[알고리즘 문제] 중복없는 구간

import java.util.*;

public class Main {

    static int arr[];

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        arr = new int[n];

        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }

        int start = 1; // start에서는 성공
        int end = n+1; // end에서는 실패

        while (start + 1 < end) {
            int mid = (start + end) / 2;
            if (check(mid)) { // mid 길이에서 중복없이 가능 한지
                start = mid;
            } else {
                end = mid;
            }
        }
        System.out.println(start);
    }

    static boolean check(int n) { // n거리에서 중복없이 가능한가?
        
        boolean isFindDuplication=false; // 첫번째 n구간에서 중복을 찾았는지 여부
        
        int num;
         int successCount = arr.length - n + 1; // n구간에서 중복이 없는 최대값, 
                                                // 일단 모두 중복이 없다고 가정
         
         List<Integer> list = new LinkedList<Integer>();
         int[] check = new int[100001];
         
         int duplicationCount=0; // 구간 내에서 중복된 숫잦의 갯수
       
        for(int i=0;i<n;i++){
          num = arr[i];
          check[num]++;
       
          if(check[num] > 1){ // 중복되는 값들을 체크해서 list에 넣어줌
            if(!list.contains(num)){
              duplicationCount++; // 처음 구간 n에서 중복된 숫자가 얼마나 있는지 
              list.add(num);
            }
            
            if(!isFindDuplication){ // 중복된 수가 있고, 아직 찾지 않았다면 successCount--;
             successCount--; 
            }
            isFindDuplication=true; // 중복되는 숫자를 한번 찾았기 때문에 true로 바꿔줌
          }
        }
        
        if(!isFindDuplication){ // 처음 n구간에서 중복을 찾지 못했다면 n구간에서는 true
          return true;
        }
      
      int index=0;
      int removeElement=0,newElement=0; // 구간을 한칸씩 전진하면서 제거/추가 되는 값
      
      for(int i=n;i<arr.length;i++){ 
        
        removeElement=arr[index++];
        check[removeElement]--;
        if(check[removeElement]==1){ 
           
           duplicationCount--;
          // 위에서 removeElement에서의 값을 --했는데, 그 값이 1이라면
          // 이 값은 원래 2였다. 이는 곧 중복된 숫자를 의미한다.
          // 그리고 중복된 숫자가 없어 졌기 때문에 duplicationCount--;
         
        }
        
        newElement=arr[i];
        check[newElement]++;

        if(check[newElement]  == 2){ 
              duplicationCount++;
        }         
          // 새로 추가된 값의 중복값이 2라는 말은, 구간내에서 중복된 값이 추가되었다는 의미이기 
          // 때문에 duplicationCount++
      
        if(duplicationCount > 0){ // 구간 내에서 중복된 숫자가 있으면, successCount--;
          successCount--;
        }
      }
      
      if(successCount > 0){ // 만약 하나라도 중복되지 않는 경우가 있다면 return true;
        return true;
      }else{
        return false;
      }
    }
}

문제는, 특정 구간내에서 중복되는 숫자가 존재하지 않는 최대 구간값을 구하는 문제이다.

예를 들어서,  [ 3 1 2 4 2 1 3 2 1 ] 라는 구간이 있을 때, 1구간 [3],[1],[2],[4]....에서는 구간 내의 숫자에 중복이 없다. 2구간 [3,1],[2,4]...에서도 역시 중복이 없다. 이렇게 구간의 크기를 늘려갔을 때, 구간에서 중복이 발생하지 않는 최대구간을 구하는 문제이다. 

 

아이디어는 매개변수탐색을 사용하였고, start(항상 중복이 없는 구간)와 end(항상 중복이 있는 구간)을 두고 그 가운데 값 mid를 사용하여 mid에서 중복이 존재하는지에 따라 start와 end의 값을 수정해 나갔다. 만약 mid구간에서 중복이 발생하지 않으면 start에 mid값을 넣어주고, mid구간에서 중복이 발생하면 end에 값을 넣어주었다.

 

[ 1 3 1 2 4 2 1 3 2 1 ]에서 구간4를 검사할 때, [1,3,1,2] -> [3,1,2,4] -> [1,2,3,2]....방식으로 꼬리 부분의 값을 제거하고 머리부분에 값을 추가하면서 앞으로 한칸씩 전진하면서 검사를 하였다.

 

구간을 검사하는 방법은, 구간내의 각 값에대해 빈도수를 확인하는 check라는 배열을 사용하였다.

 

1. 만약 꼬리부분의 값을 제거하는데 즉 check[꼬리값]을 하는데, 만약 그 값이 1이라면  2->1이 된 경우이므로 구간에 중복된 경우가 하나 줄어 들었다는 의미이다. 때문에 duplicationCount(구간내에서 중복된 숫자의 개수)를 하나 빼준다.

 

2. 만약 머리부분에 값을 추가하는데, 즉 check[머리값]을 하는데 만약 그 값이 2라면 1->2가 된 경우이므로 구간에 중복된 경우가 하나 늘었다는 의미이다. 때문에 duplicationCount(구간내에서 중복된 숫자의 개수)를 하나 더해준다. 

 

그리고 현재 구간내에서 duplicationCount > 0인 경우는 중복된 값이 있다는 의미이기 때문에 successCount--을 해준다.

 

마지막으로 successCount > 0인 경우는 구간을 전진하면서 적어도 하나의 구간에서는 중복이 존재하지 않는 다는 말이기 때문에 return true, 그렇지 않은 경우는 return false를 한다.

 

 

 

이 문제에서 가장 어려웠던 부분은, 구간내에서 중복되는 경우가 있는지 없는지 확인하는 부분이였다.

처음에는 그냥 2중 for문을 써서 한번 해보았는데 당연히 시간초과가 나왔다. 생각했던 방법은 구간을 하나씩 "검사"하는 것보다 구간내에서 중복되는 값이 "몇개"있는지 확인하는 것이였다. 중복되는 값의 개수가 0개면 해당 구간에서는 중복이 없는 것이고, 그렇지 않으면 중복된 구간이 되기 때문이다. 

 

그래서 구간을 앞으로 전진하면서 머리,꼬리 부분에 값을 하나씩 추가/삭제 할때마다 추가했을 때 해당 숫자의 빈도수가 2가 되는지, 삭제 했을 때, 해당 숫자의 빈도수가 1이 되는지를 검사하여서 중복되는 경우를 해결하였다.