[JAVA] 백준 20922 겹치는 건 싫어

https://www.acmicpc.net/problem/20922

20922번: 겹치는 건 싫어

 

1. 서론

 

되게 전형적이고 별로 어렵지도 않은 투 포인터 문제인데 더럽게 오래 걸린 문제이다. (다 소인이 부족한 탓입죠, 예)

 

2. 문제 풀이

 

N개의 수열이 주어진다. 그 연속된 수열 중 (순서 바꾸기 금지) 같은 값이 k개 보다 많으면 연속 수열이 끊긴다. 주어진 수열에서 이 연속 수열의 최댓값을 구하는 문제이다.

 

ex)

9 2
3 2 5 5 6 4 4 5 7

3 2 5 5 6 4 4

=> 7

뒤에 5가 포함되는 순간 5가 세 번 포함 되기 때문에 2보다 커져서 연속 수열이 아니게 된다. 

 

주어진 예제로 문제 이해 자체는 쉬웠는데 정답률이 왜 이리 낮을까 했는데 나도 그 정답률이 낮아지는데 일조를 하게 되었다^^

 

투 포인터를 이용해 start, end 두 개의 포인터를 이용해서 처음에는 end값을 움직이다가 k개보다 cnt 한 값이 커지는 순간 start 포인터를 움직이고 이런 작업을 반복하면서 최댓값을 갱신하면 되겠다고 생각했다.

 

=> 이 아이디어 자체가 틀린 것이 아니지만 이걸 실제로 구현하는데는 문제가 있었다. (구현 능력 부족으로, if문 위아래를 틀린다던가 범위 설정이 틀렸다던가.. ㅠㅠ 범위 지정하는 게 쉽지 않았다.)

그리고 k개보다 커지지 않고 끝나는 경우도 있고, 마지막에 end가 배열의 마지막 값에 이르르면 그때도 max값을 갱신해야 한다.

 

=> 당연한거 아니냐고? (그니까.. 근데 생각 없이 짜고, 예제가 진짜 단순하다 보니 그것조차 생각이 안나더군요)

 

질문게시판의 테케로 코드를 뜯어고쳤읍니다.

https://www.acmicpc.net/board/view/74687

글 읽기 - 제가 만든 반례 Case 모음

 

각설하고 코드를 봅시다.

 

3. 코드 설명

 

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

public class Main {

  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    StringTokenizer st = new StringTokenizer(br.readLine());
    int n = Integer.parseInt(st.nextToken());
    int k = Integer.parseInt(st.nextToken());

    int[] a = new int[n];
    st = new StringTokenizer(br.readLine());
    for (int i = 0; i < n; i++)
      a[i] = Integer.parseInt(st.nextToken());

    int[] cnt = new int[100001]; //배열 안의 값들이 몇 번 나왔는지 계수정렬 식으로 체크
    int s = 0, e = 0, ans = 0; //start, end 투 포인터
    while (true) {
      if (e < n) //end포인터가 가리키는 값을 cnt
        cnt[a[e]]++;

      if (cnt[a[e]] > k) { // k보다 크다면?
        ans = Math.max(ans, e - s); //시작~끝점 갱신 (원래는 0부터 시작해서 +1 해야 하지만 이미 범위를 넘은 상태라 -1을 해야 해서 안해줌)
        while(true) {
          cnt[a[s]]--;
          s++;
          if (cnt[a[e]] == k) break; //현재 카운트된 값이 k개만큼 줄어들때까지 s포인터 앞으로 이동
        }
      }

      if (e < n - 1)
        e++; //e 포인터 이동
      else {
        ans = Math.max(ans, e - s + 1); //e 포인터가 마지막까지 왔다면 현재 s~e값 계산 후 갱신
        break;
      }
    }

    System.out.print(ans);
  }
}

 

아이디어 자체는 위에 적었던 것처럼 end포인터를 앞으로 움직이다가 조건에 걸리면 start를 움직이며 cnt를 조정해서 답을 구하는 식이다. (자세한 내용은 주석 참조)

 

근데 처음에 cnt 함과 동시에 e++를 했다가 그러면 cnt 체크할 때 이미 e값이 바뀌기 때문에 순서를 분리했다.

그리고 start값도 처음에는 start값이 가리키는 값이 end가 가리키는 값과 같아질 때까지 start를 이동했는데 그럴 필요 없이 그냥 k개가 될 때까지만 줄이면 됐다. (그렇게 하면 이미 현재의 두 값이 같아서 이동하지 않는 경우도 생길 수도 있기 때문에)

 

억지로 조건 때려서 풀긴 했는데.. 속 시원하진 않지만 꽤 성과가 있다고 느껴 블로그에 기록합니다.