[알고리즘 10.2.4] 매개 변수 탐색 - 중복 없는 구간

문제

---

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

//배열 방문 처리를 0과 1을 사용하지 않고
// 0과 1을 사용하기 때문에 또 0으로 초기화 해줘야해서
// 타임루프가 생김.
#include <stdio.h>
 
const int max = 100005;
int arr[max];
int crr[max] = {false,};
int n;
int result=0;
int arrcount = 2;
 
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;
  //printf("%d/////\n",mid);
  
  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;
        //printf("*%d ",arr[j]);
        count++;
        if(count==mid){
          count=0;
          find=1;
          break;
        }
        
      }else{
        count=0;
        arrcount++;
        break;
      }
     // printf("\n");
    }
    
    arrcount++;
    
    //printf("\n");
    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;
}