10. 중복 없는 구간

문제

---

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

 

문제풀이

 

#include <stdio.h>

int n;
int arr[100005];
int crr[100005]={false,};
int arrcount=2;
int result=0;

void binary(int arr[],int s,int e){
  
  if(s>e||e==1){
    result = e;
    return;
  }
  
  int mid = (s+e)/2;
  int find = 0;
  int count =0;
  
  for(int i=0;i<=n-mid;i++){
    
    for(int j=i;j<mid+i;j++){

      if(crr[arr[j]]!=arrcount){

        crr[arr[j]] = arrcount;
        
        count++;
        
        if(count==mid){
          count = 0;
          find = 1;
          break;
        }
      }
      else{
        count = 0;
        arrcount++;
        break;
      }
    }
    arrcount++;
    
    if(find==1){
      result=mid;
      break;
    }
  }
  
  if(find == 1){
    binary(arr,mid+1,e);
  }else{
    binary(arr,s,mid-1);
  }
}

int main() {

  scanf("%d",&n);
  for(int i=0;i<n;i++){
    scanf("%d",&arr[i]);
  }
  
  binary(arr,0,n);
  printf("%d",result);
  
  return 0;
}