[실전 문제] 중복 없는 구간

1. 문제

n개의 숫자가 주어지고, 이 중에서 r개의 연속된 숫자를 선택했을 때, 이 연속 부분 내에는 숫자가 중복되지 않기를 원한다. 예를 들어, 다음과 같이 10개의 숫자에서 3개의 연속된 숫자를 선택할 수 있다.

이렇게 선택을 하면, 선택된 숫자들 사이에서는 중복이 존재하지 않는다. r의 최댓값을 구하는 프로그램을 작성하시오. 위의 경우, (4, 2, 1, 3)을 선택하면 되므로 r의 최댓값은 4이다. r이 5 이상이 될 경우, 중복 없이 연속 부분을 선택하는 것이 불가능하다.

---

입력

첫째 줄에는 숫자의 개수 n이 주어진다. ( 1 ≤ n ≤ 100,000 ) 둘째 줄에 n개의 숫자가 주어진다. 각 숫자는 항상 1보다 크거나 같고, n보다 작거나 같다. 

출력

r의 최댓값을 출력한다.

예제 입력

case 1)

10
1 3 1 2 4 2 1 3 2 1

 

case 2)

7
7 1 4 2 5 3 6

예제 출력

case 1) 4

case 2) 7

 

 

 

2. 풀이

이 문제를 풀기 위해서는 2 가지의 특징을 알아야한다.

 

우선, 예시를 통해 본다면

1

3

1

2

4

2

1

3

2

1

• '3 - 1 - 2 - 4'를 확인했을 때, 중복이 없고 길이가 4이다.

 

이 구간에서 다시 살펴본다면,

• '3 - 1 - 2'를 확인했을 때, 중복이 없고 길이가 3이다.
• '3 - 1'를 확인했을 때, 중복이 없고 길이가 2이다.

 

그렇다면 반대로 길이가 5인 경우를 보면, 아무리 살펴보아도 중복이 없는 구간이 없다. 즉, 길이가 5, 6, 7, 8, 9, 10인 경우는 모두 안된다는 뜻이다.

 

다시 정리하자면 이렇게 볼 수 있다.

• 길이가 4 이하인 구간들은 모두 중복이 없는 구간들이다.
• 길이가 5 이상인 구간들은 모두 중복이 있는 구간들이다.

 

이를 각 길이에 대해 중복이 없는 구간을 O, 중복이 있는 구간을 X라고 한다면 다음과 같다.

1	2	3	4	5	6	7	8	9	10
O	O	O	O	X	X	X	X	X	X

 

길이에 대한 표에서 4와 5의 경계선만 안다면 충분히 답을 구할 수 있다는 것을 확인했다면, 어떻게 찾는지를 고민해보아야 한다. 여기서 부터는 간단한 문제다. 길이에 대한 표를 이진 탐색을 이용하면 빠르고 쉽게 구할 수 있다.

 

위의 예제로는, 길이 1에서 10까지의 중간 길이인 5를 선택했을 때의 구간이 가능한지 가능하지 못하는지 확인을 하면 된다. 길이가 5인 구간이 불가능하기 때문에 5 이상은 모두 안된다는 뜻이고 5 미만의 길이는 모두 가능하다는 뜻이다.

 

하지만 이 문제를 풀 수 있는 아이디어를 얻었음에도 이 문제를 통과하기에는 힘들다. 그 이유는 시간 복잡도이다. 우선 위의 아이디어에서 이진 탐색을 적용했기 때문에 logN 만큼의 시간 복잡도를 가지지만, 5인 구간일 때의 중복이 없는 구간과 있는 구간을 모든 경우의 수를 통해 알아내는데 O(N^3)이 걸린다. 결국 O(N^3) + logN 만큼의 시간이 소요된다는 점이다.

 

따라서 O(N^3)의 시간을 줄이기 위한 방안을 찾아야한다. 이 경우, 각 숫자의 개수를 세어보면 된다.

 

구간의 길이가 5인 경우를 생각한다면,

'1 - 3 - 1 - 2 - 4'
1의 갯수	2의 갯수	3의 갯수	4의 갯수	5의 갯수	6의 갯수	7의 갯수
2	1	1	1	0	0	0

'3 - 1 - 2 - 4 - 2'
1의 갯수	2의 갯수	3의 갯수	4의 갯수	5의 갯수	6의 갯수	7의 갯수
1	2	1	1	0	0	0

'1 - 2 - 4 - 2 - 1'
1의 갯수	2의 갯수	3의 갯수	4의 갯수	5의 갯수	6의 갯수	7의 갯수
2	2	0	1	0	0	0

'2 - 4 - 2 - 1 - 3'
1의 갯수	2의 갯수	3의 갯수	4의 갯수	5의 갯수	6의 갯수	7의 갯수
1	2	1	1	0	0	0

등등 2가 있는 경우는 모두 중복이 되는 구간임을 알 수 있다.

 

하지만 길이가 5인 구간을 모두 도는데 O(N), 각 숫자의 갯수를 담은 배열에 2가 있는지 확인하는데 O(N)으로, 이진탐색까지 생각한다면 총 O(N^2) + logN 의 시간 복잡도가 소요된다. 여전히 시간 복잡도가 크기 때문에 이를 더 줄여야한다.

 

이 경우, 2 이상인 갯수를 세기 위해 사용되는 O(N)의 시간 복잡도를 O(1)로 줄이면 된다. 이를 위한 아이디어로는, 값이 2 이상인 원소의 개수를 기억하면 된다.

'1 - 3 - 1 - 2 - 4'
1의 갯수	2의 갯수	3의 갯수	4의 갯수	5의 갯수	6의 갯수	7의 갯수
2	1	1	1	0	0	0
2의 갯수 = 1

'3 - 1 - 2 - 4 - 2'
1의 갯수	2의 갯수	3의 갯수	4의 갯수	5의 갯수	6의 갯수	7의 갯수
1	2	1	1	0	0	0
2의 갯수 = 1

'1 - 2 - 4 - 2 - 1'
1의 갯수	2의 갯수	3의 갯수	4의 갯수	5의 갯수	6의 갯수	7의 갯수
2	2	0	1	0	0	0
2의 갯수 = 2

'2 - 4 - 2 - 1 - 3'
1의 갯수	2의 갯수	3의 갯수	4의 갯수	5의 갯수	6의 갯수	7의 갯수
1	2	1	1	0	0	0
2의 갯수 = 1

또한 이 과정에서 중요한 부분중 하나는, '1 - 3 - 1 - 2 - 4'에서 '3 - 1 - 2 - 4 - 2'로 가면서 1의 갯수는 감소하고 2의 갯수는 증가하는 것 처럼, 첫 요소에 대한 갯수는 1 감소하고 새로 들어온 요소에 대한 갯수는 1 증가한다는 부분도 생각해주어야한다.

 

결국, 2의 원소의 갯수를 세어 구간이 가능한지 불가능한지 O(1)의 시간복잡도로 알 수 있다. 즉, 2 이상인 원소의 개수가 0인 경우에 가능함을 알 수 있다.

---

다시 위의 모든 것을 문장으로 정리한다면 다음과 같다.

• 이진 탐색을 통해 중복이 없는 구간과 있는 구간을 O(logN)만의 시간으로 알 수 있다.
• 해당 길이가 가능한지, 가능하지 않은지에 대해 판별을 하는 방법은 각 숫자의 갯수를 통해 알 수 있다.
• 각 숫자의 갯수를 알아냈을 때, 각 숫자의 갯수가 2인 갯수를 구하여 O(1)만의 시간으로 문제를 해결할 수 있다.

import java.io.*;
import java.util.StringTokenizer;

public class Main {

    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    private static int n;
    private static int[] arr;
    private static int[] arrCount; // arr의 각 숫자의 개수를 저장하는 배열

    public static void main(String[] args) throws IOException {

        n = Integer.parseInt(br.readLine());

        arr = new int[n+1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 1; i <= n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int s = 1;
        int e = n;

        if(!isOverlap(s)) {
            bw.write(s + "");
            bw.flush();
            return;
        }
        if(isOverlap(e)) {
            bw.write(e + "");
            bw.flush();
            return;
        }

        while(s + 1 < e) {
            int mid = (s + e) / 2;

            if(isOverlap(mid)) s = mid;
            else e = mid;
        }

        bw.write(s + "");
        br.close();
        bw.flush();
        bw.close();
    }

    private static boolean isOverlap(int interval) {
        int s = 1;
        int arrCountTwo = 0;
        arrCount = new int[n+1];
        for(int i = s; i < s + interval; i++) {
            arrCount[arr[i]]++; // arr의 각 숫자의 개수를 저장

            if(arrCount[arr[i]] >= 2) { // arr의 각 숫자의 개수가 2 이상일 경우
                arrCountTwo++;
            }
        }

        if(arrCountTwo == 0) {
            // arr의 각 숫자의 개수가 2 이상인 요소가 없다면 중복이 되는 구간이 없다는 뜻
            return true;
        }

        // 1부터 5까지 검사가 끝났다면
        // 2부터 6까지 검사 시작을 위한 반복문
        // 첫 요소에 대한 갯수는 1 감소하고 새로 들어온 요소에 대한 갯수는 1 증가
        while(s + interval < n) {

            arrCount[arr[s]]--;
            if(arrCount[arr[s]] >= 1) {
                arrCountTwo--;
            }

            s++;

            arrCount[arr[s + interval - 1]]++;
            if(arrCount[arr[s + interval - 1]] >= 2) {
                arrCountTwo++;
            }

            if(arrCountTwo == 0) return true;
        }
        return false;
    }
}