[백준 / #23567 / C++] Double Rainbow

이 문제는 ICPC 2021 기출문제이다.

 

https://www.acmicpc.net/problem/23567

23567번: Double Rainbow

 

투 포인터를 공부하기 아주 좋은 문제라고 생각된다.

 

 

문제 해석:

 

 

 영어 해석에 어려움을 겪는 분들을 위해 최대한 자세히 쓰겠다. 이 문제는 쉽게 풀어 쓰면 구간을 찾고 가능한 구간들 중

 

최소 길이를 구하는 문제이다. 문제에서 주어진 k는 색의 가지수를 말하는데 k가 4이면 1, 2, 3, 4 총 4가지의 색을 가지고

 

있다는 것을 의미한다. 구간의 조건은 p와 p`이 각각 최소 한 개씩 모든 색을 가지고 있으면 double rainbow가 생기고 이 때

 

의 구간 길이 중 최소 길이를 구하라는 의미의 문제이다. 따라서 구간을 구해야 한다는 부분에서 힌트를 얻어 투포인터를

 

활용하면 되는 문제임을 눈치 챌 수 있다. 투포인터에서 약간의 예외를 조심해주면 쉽게 풀린다.

 

 

 

알고리즘 해설 및 코드:

 

 

 우선 left와 right가 각각 배열의 처음 부분에서 시작되도록 한다. left와 right가 맨 왼쪽 배열의 처음에 존재한다는 의미는

 

p[]에서 p[0]가 p`의 구간이 되었음을 의미한다. 만일 이렇게 해서 p`의 구간이 k개의 색을 갖지 못한다면 right를 한 칸 이동

 

시켜준다. 그렇게 하나씩 늘려가며 p`의 구간이 k개의 색을 가진다면 이번에는 p의 색이 k개의 색을 갖는지 확인해주고 만

 

약 갖지 않는다면 left를 하나씩 늘려가며 k개의 색이 되는지 확인해준다. 이유는 p`이 이동하며 p 구간의 색을 가져갔으므

 

로 하나씩 돌려주며 p와 p`이 k개의 색을 같는 즉, double rainbow가 성립하는 구간을 찾아주는 것이다.

 

 

 그러다 만약 p와 p`이 둘 다 k개의 색을 갖는 구간을 찾으면 right - left + 1의 크기가 만약 ans[0]보다 작으면 ans[0]의 값을

 

바꿔준다. 하지만 다른 구간이 최솟값을 가질 수도 있으므로 계속해서 연산을 해주어야한다. 따라서 right를 하나씩 증가시

 

켜주며 마찬가지로 loop를 돌며 새로운 구간을 찾아주는 것이다. 이것으로 문제를 해결할 수 있다.

 

 

 

 

투포인터 알고리즘만 알고 있다면 금방 풀릴 문제라고 생각한다. 필자는 교수님께서 문제를 내주셨을때 풀지 못했지만 다

 

시 풀어보니 금방 풀리는 문제였다.