백준 15961 회전 초밥

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

문제 이해

k개의 연속된 숫자를 갖는 Subset을 탐색하는 문제입니다.
문제 예시 그림은 Circular Linked List처럼 표현되었지만, 꼭 Circular Linked List로 구현할 필요는 없습니다. 인덱스를 나머지 연산으로 처리해 연결된 것처럼 만들면 됩니다.
- 예를 들어, k = 4 일 때 [n - 1, n, n + 1, n + 2] 배열은 [n - 1, 0, 1, 2]와 동일합니다.

접근 방법

이 문제는 배열의 길이가 무려 3백만이 될 수도 있는 상당히 큰 규모의 입력이 주어집니다. 그러므로 머릿속에 가장 먼저 떠오르는
```
for i in range(N):
  for subset in original[i:i+k]:
    do_count
```
이런 구조의 코드를 작성한다면 높은 확률로 시간 초과를 마주칠 것입니다.
길이가 k인 subset의 양 끝을 나타낼 인덱스 int left, right를 활용하는 투포인터 문제로 접근합니다.
전체 데이터를 모두 확인해야 하므로 subset을 오른쪽으로 한 칸씩 옮겨가며 탐색하는 슬라이딩 윈도우를 활용합니다.
만약 인덱스가 배열 길이 N보다 같거나 커진다면 IndexOutOfBoundsException 방지를 위해 나머지(modulo) 연산을 해줍니다.
현재 subset에 나온 초밥의 가짓수를 출력하는데, subset 안에 c가 없다면 +1을 하여 출력합니다.

코드

public class Main {

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

        // 문제 입력
        int N = Integer.parseInt(st.nextToken());
        int d = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());

        // 회전 초밥 벨트에 높인 초밥 종류 입력
        int[] sushi = new int[N];
        for (int i = 0; i < N; i++) {
            sushi[i] = Integer.parseInt(br.readLine());
        }

        // 현재 Subset의 초밥 가짓수를 카운트 할 맵 선언
        Map<Integer, Integer> subsetCount = new HashMap<>();

        // 투 포인터 설정하고 k - 1까지 카운트
        // 만약 k = 4이면 [0, 1, 2] 까지만 확인하고
        // 3부터는 while문에서 핸들링
        int left = 0, right = 0;
        for (; right < k - 1; right++) {
            int sr = sushi[right];
            // 맵에 이 종류가 없으면 k,v 쌍 초기화 (NullPointerException) 방지
            subsetCount.putIfAbsent(sr, 0);
            // 가짓수 + 1
            subsetCount.put(sr, subsetCount.get(sr) + 1);
        }

        int maxSubsetCount = 0;
        while (right < N + k) {
            // 오른쪽 포인터 있는 칸의 초밥까지 카운트
            // 포인터 위치가 N보다 클 수 있으므로 나머지 연산 거침
            int rightModulo = right % N;

            int sr = sushi[rightModulo];
            subsetCount.putIfAbsent(sr, 0);
            subsetCount.put(sr, subsetCount.get(sr) + 1);

            // 현재 subset의 초밥 종류는 map의 keySet의 크기와 같음
            // 예를 들어 현재 초밥 종류가 [1, 2, 1, 3]이라면
            // 맵의 상태는 {1: 2, 2: 1, 3: 1}일 것
            // 그러면 keySet은 [1, 2, 3]이 반환됨
            int thisSubsetCount = subsetCount.keySet().size();
            // 만약 현재 subset에 쿠폰과 동일한 초밥 종류가 없으면
            // 쿠폰으로 하나 더 먹을 수 있음
            thisSubsetCount += subsetCount.containsKey(c) ? 0 : 1;
            // 더 큰 값으로 업데이트
            maxSubsetCount = Math.max(maxSubsetCount, thisSubsetCount);

            // subset 전체를 한 칸 오른 쪽으로 옮기기
            // 현재 left가 가리키고 있던 초밥 종류를 -1 해주는데
            int leftModulo = left % N;
            int sl = sushi[leftModulo];
            int l = subsetCount.get(sl);

            // [2, 1, 3, 1]과 같이 이번 left를 빼면 0개인 경우는 맵에서도 삭제
            // {1: 2, 2: 1, 3: 1} -> {1: 2, 3: 1}
            if (l == 1) subsetCount.remove(sl);
            // 위 [1, 2, 1, 3] 예시처럼 -1 해도 남아있으면 값만 업데이트
            else subsetCount.put(sl, l - 1);
            left += 1;
            // 새 right는 이 while문 시작 시 다룸
            right += 1;
        }
        System.out.println(maxSubsetCount);
    }
}

결과

이번 문제도 다른 투포인터 문제인 백준 5525 IOIOI를 풀어본 경험이 있어 아이디어를 떠올리기 수월했습니다. 5525번 문제에서는 부분 성공만 했는데 이 문제는 한 번에 통과해서 기분이 좋네요 😀

Prerequisites: 이 글에서 언급되었으나 깊게 설명하지 않은 내용입니다.
Circular Linked List
Two pointers
Sliding Window