중복 없는 구간

문제

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

 

// 코드

import java.util.*;
import java.io.*;
 
public class Main{
  
  static int n;
  static int[] arr;
  static int[] arrCnt;
  static int start, end;
  static int maxSum = 0, maxIdx = 0;
  
  // 1. 초기의 누적합을 구해주는 메서드
  static boolean isDuplicate(int interval) {
    boolean flag = false;
    // 중복된 숫자의 개수를 카운팅한다.
    int cnt = 0;
    
    for(int i=0; i<interval; i++) {
      arrCnt[arr[i]] += 1;
      // 중복 됐냐 안됐냐만 판단하기 때문에
      // arrCnt의 값이 2를 넘는지 안넘는지만 체크한다.
      if(arrCnt[arr[i]] == 2) {
        cnt++;
      }
    }
    
    if(cnt == 0) flag = true;
    
    for(int i=0; i<n-interval; i++) {
      // 중복이였지만 -1을 하였을 때 중복이 아닌 경우 -1을 해준다.
      if(arrCnt[arr[i]] >= 2 && arrCnt[arr[i]] - 1 == 1) cnt--;
      arrCnt[arr[i]]   -= 1;
      arrCnt[arr[i+interval]] += 1;
      // arrCnt의 값이 중복이 되는 순간 +1해준다.
      if(arrCnt[arr[i+interval]] == 2) cnt++;
      
      if(cnt == 0) flag = true;
    }
     
    return flag;
  }
  
  
  public static void main(String[] args) throws Exception {
 
    // Please Enter Your Code Here
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    
    n      = Integer.parseInt(br.readLine());    
    arr    = new int[n];
    
    // 구간별 개별 숫자의 빈도수를 카운팅하는 배열을 만든다.
    // 반환 값이 true : 중복이 아니다, false : 해당 구간은 중복이다.
    int maxSize = -1;
    StringTokenizer st = new StringTokenizer(br.readLine());
    for(int i=0; i<n; i++) {
      arr[i] = Integer.parseInt(st.nextToken());
      if(maxSize < arr[i]) maxSize = arr[i];
    }
    
    
    // 구간의 시작점과 끝점
    start = 0;
    end   = n+1;
    
    int resInterval=1, resMax=0;
    
    while(start+1 < end) {
      arrCnt = new int[maxSize + 1];
      
      int mid = (start + end) / 2;
      boolean getFlag = isDuplicate(mid);
      
      // mid값을 넣었을 때 
      // 해당 구간이 중복이면 이후의 구간은 모두 중복이다.
      // 그래서 중복이 아니면 start값이 바뀌고
      // 중복이 아니면 end값이 바뀐다.
      if(getFlag) {
        start = mid;
        resInterval = mid;
      }
      else {
        end = mid;
      }
      
    }
    bw.write(String.valueOf(resInterval));
    
    br.close();
    bw.flush();
    bw.close();
  }
}