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

접근

C언어나 C++을 써본 사람이라면 투포인터를 이해하기가 더 쉬울 것이라고 생각한다. 포인터는 말 그대로 어떤 배열을 '가리키는' 화살표를 사용하는 것이다. 그런데 자바에는 포인터가 없으므로, 배열의 특정 위치를 가리키는 값, 즉 인덱스로 보면 된다. (자바에 포인터가 없는 이유도 나중에 정리해보면 좋을 것 같다.)

이 문제에서는 조건을 만족하는 가장 긴 수열의 길이를 찾는 것이 목적이기 때문에, 해당 수열을 찾기 위해 수열의 양 옆을 가리키는 left와 right라는 두 포인터(인덱스값)를 이용하게 된다. 포인터를 한칸씩 이동하며 left ~ right에 해당하는 부분 수열이 문제에서 제시하는 조건에 부합한다면 결과(answer) 값을 갱신하면 된다. 각 숫자의 개수를 카운팅하는 방법은 여러 방법이 있을 것이다. 20만 크기의 배열을 선언하여 바로바로 참조하는 방법도 있겠지만, 나는 굳이 빈 공간을 두기 싫어서 숫자 N을 키로 갖는 Map을 사용했다.

첫 번째 예제에서는 k값이 2이기 때문에, 어떤 숫자의 개수가 2가 되기 전까지는 계속해서 right를 증가시켜 준다. 그래야 left~right 수열의 길이가 최대가 되기 때문이다. 그렇게 한 칸씩 이동하다가 (3, 2, 5, 5, 6, 4, 4, 5) 에서 조건에 위배되는 경우를 마주치게 되었다. 그러면 앞에 나온 동일한 숫자 5가 없을 때까지 left를 이동시켜줘야 하므로, 앞부분의 (3, 2, 5) 를 제외하고(카운팅한 개수에서도 하나씩 없앰) left는 4번째 자리의 5를 가리키게 된다. 이제 K값보다 큰 개수의 숫자가 없기 때문에 다시 조건에 맞는 가장 긴 순열을 찾기 위해 right를 증가시키는 과정을 입력 순열의 마지막 인덱스가 될 때까지 반복하면 된다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        int answer = 1; // k의 최솟값은 1임

        // 기본 입력값 받기
        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        // 입력 수열 저장
        int[] arr = new int[n];
        st = new StringTokenizer(br.readLine());

        for (int i = 0; i < n; i++)
            arr[i] = Integer.parseInt(st.nextToken());

        // 투 포인터 적용
        Map<Integer, Integer> m = new HashMap();
        int left = 0, right = 0; // left~right의 연속된 수열을 위한 인덱스

        while(right < n) { // 입력수열의 마지막까지 확인
            m.put(arr[right], m.getOrDefault(arr[right], 0) + 1);

            while (m.get(arr[right]) > k) {
                m.put(arr[left], m.get(arr[left]) - 1);
                left++;
            }
            
            answer = Math.max(answer, right - left + 1);
            right++;
        }
        System.out.println(answer);
    }

}