문제
n개의 숫자가 주어지고, 이 중에서 r개의 연속된 숫자를 선택했을 때, 이 연속 부분 내에는 숫자가 중복되지 않기를 원한다. 예를 들어, 다음과 같이 10개의 숫자에서 3개의 연속된 숫자를 선택할 수 있다.
이렇게 선택을 하면, 선택된 숫자들 사이에서는 중복이 존재하지 않는다. r의 최댓값을 구하는 프로그램을 작성하시오. 위의 경우, (4, 2, 1, 3)을 선택하면 되므로 r의 최댓값은 4이다. r이 5 이상이 될 경우, 중복 없이 연속 부분을 선택하는 것이 불가능하다.
입력
첫째 줄에는 숫자의 개수 n이 주어진다. ( 1 ≤ n ≤ 100,000 ) 둘째 줄에 n개의 숫자가 주어진다. 각 숫자는 항상 1보다 크거나 같고, n보다 작거나 같다.
출력
r의 최댓값을 출력한다.
예제 입력
10
1 3 1 2 4 2 1 3 2 1
예제 출력
4
예제 입력
7
7 1 4 2 5 3 6
예제 출력
7
이 문제는 길이 1부터 N 까지 탐색하면 풀수 있는 문제 이지만, 입력의 범위가 10,000까지 이기 때문에 그렇게 풀게 되면 시간초과가 나온다. 그래서 시간을 줄여야 하는데 이진탐색으로 매개변수탐색을 하고, 중복인 구간을 확인할때에도 구간의 숫자를 하나하나씩 보면 안되기 때문에 이부분에서도 생각이 필요하다.
이진탐색을 이용하여 매개변수 탐색을 하는법을 먼저 말해보면, 길이 1과 N을 검사했을때 중복인 구간이 있는지 없는지를 봐야한다. 근데 1은 중복구간이 될수가 없기 때문에 start를 1로 설정할 수 있고, N을 검사했을때 중복인 구간이 있다면 end를 N으로 놓는다. 즉 무조건 중복인 구간이 없는 길이에 start를 놓고, 중복인 구간이 있는 길이에 end를 놓는다. 만약에 길이 N을 검사했을때 중복인 구간이 없다면 N을 출력하고 답으로 정하면 된다. 그러면 이제 매개변수탐색을 하면 되는데, 중복인 구간이 없다면 더 큰 구간을 봐서 최대값을 구해야 하고, 중복인 구간이 있다면 더 작은 값을 확인해야 한다. 그래서 이진탐색으로 start와 end 나란히 놓일 때, start를 답으로 정하면 된다. 간단하게 그림으로 표현해보면
길이 -> 1 2 3 4 5 6 7 8 9 10
start end
이 경우에 4를 중복인 구간이 없는 길이의 최대값으로 설정할 수 있다. 위의 방법을 이진탐색으로 구현하면 된다.
이제는 중복인구간을 검사할 때 시간을 줄여야 하는데, 위의 예제에서 길이 4짜리 구간을 먼저 검사하여 cnt 배열의 인덱스에 해당하는 숫자를 증가시킨다. 처음 길이 4짜리를 보면 cnt 배열은
[0] [1] [2] [3] [4]
cnt 2 1 1
이렇게 되있을 것이다. 이제 여기에서 x변수를 선언해서 중복인 숫자의 개수를 넣는다. 즉 위의 경우에는 1이 2개가 있기 때문에 x는 1이 된다. 처음길이에 해당하는 것은 어쩔수 없이 한번씩 다 돌아야 하지만, 그다음부터는 그렇지 않아도 된다. 왜냐하면 다음으로 넘어갈 때 1을 빼주고 4를 더하면 되기 때문이다. 이것을 표현해보면
[0] [1] [2] [3] [4]
cnt 1 1 1 1
이렇게 된다. 그러면 이제 cnt[1] 부분이 2에서 1로 줄었으므로 변수 x를 -1 해주고, cnt[4]부분이 1늘었지만 2개가 아니기 때문에 x는 변화가 없다. 즉 x는 0이되는데 그러면 중복되는 숫자가 없는 뜻이기 때문에 길이 4가 중복없는구간이라고 판단할 수 있다. 이렇게 처리하면 O(1)에 처리할 수 있다.
풀기까지 여러 아이디어가 필요하고, 생각할 것이 많이 때문에 배울점이 많은 문제라고 생각한다. 또 중복구간을 탐색할때 이렇게도 유용하게 할수있다는 것도 배울수있었고, 매개변수탐색도 어려워서 공부할 부분이 많은것 같아서 까먹지말고 알아둬야겠다.
