[백준 #2531] 회전초밥

1. 문제 설명

2. 해설

문제를 이해하는게 조금 어려웠다. 쿠폰 사용 기준을 이상하게 이해했더니 문제가 안 풀리지...

아무튼, 이 문제는 기본적으로 투 포인터로 접근 가능하지만 일정 크기의 윈도우를 끝까지 밀어가면서 푸는 슬라이딩 윈도우 기법으로 접근해도 된다. 연속해서 k개의 접시만 먹을 수 있으니까.

문제는 간단하다. 0번째 인덱스부터 k 크기의 윈도우를 끝까지 밀면서, 윈도우 안에 쿠폰으로 먹을 수 있는 초밥이 포함되어 있으면 넘어가고, 없으면 먹을 수 있는 초밥 종류를 1개 늘려주면서 최대로 먹을 수 있는 초밥 종류를 찾아주면 된다.

위의 문제 설명대로 초밥을 (9, 7, 30, 2), (30, 2, 7, 9), (2, 7, 9, 25) 이렇게 먹는다고 할 때, 앞의 두 가지 경우는 윈도우 안에 쿠폰으로 먹을 수 있는 30번 초밥이 있기 때문에 그대로 먹으면 되고, (2, 7, 9, 25) 같은 경우는 쿠폰을 안 썼으니 서비스로 30번 초밥을 준다고 생각하면 이해가 빠를지도? 그래서 앞의 두 가지는 초밥 종류가 4종류이고, 마지막 경우는 초밥 종류가 5가지인 것이다.

3. 정답 코드

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

public class Main {
    static int[] arr;
    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 d = Integer.parseInt(st.nextToken()); // 가지수
        int k = Integer.parseInt(st.nextToken()); // 연속으로 먹는 접시 수
        int c = Integer.parseInt(st.nextToken()); // 쿠폰 써서 공짜로 먹는 메뉴

        arr = new int[n];


        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        System.out.println(twoPointer(n, k, c, d));
    }

    static int twoPointer(int N, int K, int coupon, int kinds) {
        int cnt = 0, maxCnt = 0;
        int[] visited = new int[kinds + 1];

        for (int i = 0; i < K; i++) { // 처음 K 크기의 윈도우 생성
            if (visited[arr[i]] == 0) {
                ++cnt;
            }
            ++visited[arr[i]];
        }

        maxCnt = cnt;

        for (int i = 1; i < N; i++) {
            if (maxCnt <= cnt) {
                if (visited[coupon] == 0) { // 쿠폰으로 먹을 수 있는 메뉴를 안 먹었을 경우
                    maxCnt = cnt + 1;
                } else {
                    maxCnt = cnt;
                }
            }

            --visited[arr[i - 1]];
            if (visited[arr[i - 1]] == 0)
                --cnt;

            if (visited[arr[(i + K - 1) % N]] == 0)
                ++cnt;

            ++visited[arr[(i + K - 1) % N]];
        }
        return maxCnt;
    }
}