백준 15961 회전 초밥

 1public class Main {
 2
 3    public static void main(String[] args) throws IOException {
 4        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 5        StringTokenizer st = new StringTokenizer(br.readLine());
 6
 7        // 문제 입력
 8        int N = Integer.parseInt(st.nextToken());
 9        int d = Integer.parseInt(st.nextToken());
10        int k = Integer.parseInt(st.nextToken());
11        int c = Integer.parseInt(st.nextToken());
12
13        // 회전 초밥 벨트에 높인 초밥 종류 입력
14        int[] sushi = new int[N];
15        for (int i = 0; i < N; i++) {
16            sushi[i] = Integer.parseInt(br.readLine());
17        }
18
19        // 현재 Subset의 초밥 가짓수를 카운트 할 맵 선언
20        Map<Integer, Integer> subsetCount = new HashMap<>();
21
22        // 투 포인터 설정하고 k - 1까지 카운트
23        // 만약 k = 4이면 [0, 1, 2] 까지만 확인하고
24        // 3부터는 while문에서 핸들링
25        int left = 0, right = 0;
26        for (; right < k - 1; right++) {
27            int sr = sushi[right];
28            // 맵에 이 종류가 없으면 k,v 쌍 초기화 (NullPointerException) 방지
29            subsetCount.putIfAbsent(sr, 0);
30            // 가짓수 + 1
31            subsetCount.put(sr, subsetCount.get(sr) + 1);
32        }
33
34        int maxSubsetCount = 0;
35        while (right < N + k) {
36            // 오른쪽 포인터 있는 칸의 초밥까지 카운트
37            // 포인터 위치가 N보다 클 수 있으므로 나머지 연산 거침
38            int rightModulo = right % N;
39
40            int sr = sushi[rightModulo];
41            subsetCount.putIfAbsent(sr, 0);
42            subsetCount.put(sr, subsetCount.get(sr) + 1);
43
44            // 현재 subset의 초밥 종류는 map의 keySet의 크기와 같음
45            // 예를 들어 현재 초밥 종류가 [1, 2, 1, 3]이라면
46            // 맵의 상태는 {1: 2, 2: 1, 3: 1}일 것
47            // 그러면 keySet은 [1, 2, 3]이 반환됨
48            int thisSubsetCount = subsetCount.keySet().size();
49            // 만약 현재 subset에 쿠폰과 동일한 초밥 종류가 없으면
50            // 쿠폰으로 하나 더 먹을 수 있음
51            thisSubsetCount += subsetCount.containsKey(c) ? 0 : 1;
52            // 더 큰 값으로 업데이트
53            maxSubsetCount = Math.max(maxSubsetCount, thisSubsetCount);
54
55            // subset 전체를 한 칸 오른 쪽으로 옮기기
56            // 현재 left가 가리키고 있던 초밥 종류를 -1 해주는데
57            int leftModulo = left % N;
58            int sl = sushi[leftModulo];
59            int l = subsetCount.get(sl);
60
61            // [2, 1, 3, 1]과 같이 이번 left를 빼면 0개인 경우는 맵에서도 삭제
62            // {1: 2, 2: 1, 3: 1} -> {1: 2, 3: 1}
63            if (l == 1) subsetCount.remove(sl);
64            // 위 [1, 2, 1, 3] 예시처럼 -1 해도 남아있으면 값만 업데이트
65            else subsetCount.put(sl, l - 1);
66            left += 1;
67            // 새 right는 이 while문 시작 시 다룸
68            right += 1;
69        }
70        System.out.println(maxSubsetCount);
71    }
72}