[BOJ] 20922 겹치는 건 싫어 - JAVA

1. 문제

20922번: 겹치는 건 싫어

홍대병에 걸린 도현이는 겹치는 것을 매우 싫어한다. 특히 수열에서 같은 원소가 여러 개 들어 있는 수열을 싫어한다. 도현이를 위해 같은 원소가 
100,000개 이하로 들어 있는 최장 연속 부분 수열의 길이를 구하려고 한다.

100,000 이하의 양의 정수로 이루어진 길이가 
N인 수열이 주어진다.  이 수열에서 같은 정수를 
K개 이하로 포함한 최장 연속 부분 수열의 길이를 구하는 프로그램을 작성해보자.

---

2. 풀이

투포인터라고 생각하고 풀었지만 다른사람들 풀이와는 조금 다르긴 한 것 같다. while문을 쓰지않고 for로 end위치를 하는 부분이 특히 다르다.

1.  start=0으로 시작해서, count배열에 해당 값을 +1하며 움직인다. 

2.  만약 count[arr[i]]가 K초과라면 start부터 i-1까지 탐색하며 arr[i]==arr[j] 일 때를 찾는다. 이 때, start 값을 j+1로 변경한다. 미리 +1해두었으므로 이 경우에 count[arr[i]]-1도 잊지않아야 한다.

3.  i가 하나 늘어날 때마다 최대길이를 갱신한다. 현재 길이는 i-start+1로 구하면 된다.

import java.io.*;
import java.util.*;

public class BOJ_20922_겹치는건싫어 {
   public static void main(String[] args) throws IOException {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(in.readLine());
      int N = Integer.parseInt(st.nextToken());
      int K = Integer.parseInt(st.nextToken());
      int[] arr = new int[N];
      st = new StringTokenizer(in.readLine());
      for(int i=0;i<N;i++) arr[i] = Integer.parseInt(st.nextToken());

      int[] count = new int[100001];
      count[arr[0]]++;
      int start = 0;
      int answer = 1;
      for(int i=1;i<N;i++){
         count[arr[i]]++;
         if(count[arr[i]]>K){
            //K 초과일 때 앞의 숫자 빼기
            for(int j=start;j<i;j++) {
               count[arr[j]]--;
               if (arr[i] == arr[j]) {
                  start = j + 1;
                  break;
               }
            }
         }
         //최대길이 갱신
         answer = Math.max(answer,i-start+1);
      }

      System.out.println(answer);
   }
}

---

3. 결과

count 배열 길이를 아무 생각 없이(,,) N+1로 했다가 인덱스 에러가 났다.

최대길이인 100000에 +1해준 길이로 정해서 통과했다.

나만 시간이 많이 걸려서 코드를 다시 살펴보니 이 부분에서 문제가 있었다. 앞의 숫자를 빼니까 당연히 count배열에서도 -1을 해야하는데 그걸 하지 않아서 필요없는 반복을 하게 된 것 같다. 이 부분을 고치고 나니 다른 사람들과 비슷한 시간대로 돌아왔다.

//K 초과일 때 앞의 숫자 빼기
for(int j=start;j<i;j++) {
   count[arr[j]]--;
   if (arr[i] == arr[j]) {
      start = j + 1;
      break;
   }
}