[Algo] 백준 2431 회전 초밥

문제 바로가기 : https://www.acmicpc.net/problem/2531

메모리 : 22960KB

시간 : 244ms

언어 : Java 11

---

코드

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

public class Main {

    public static <T> 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[] susi = new int[N];
        Map<Integer, Integer> ateDish = new HashMap<>();
        Set<Integer> susiType = new HashSet<>();
        for (int i = 0; i < N; i++) {
            susi[i] = Integer.parseInt(br.readLine());
        }
        ateDish.put(c, 1);
        susiType.add(c);
        int answer = 0;
        int left = 0;
        int right = 0;
        int cnt = 0;
        while (left < N) {
            int idx = right % N;
            susiType.add(susi[idx]);
            if (ateDish.containsKey(susi[idx])) {
                ateDish.computeIfPresent(susi[idx], (key, value) -> value + 1);
            } else {
                ateDish.put(susi[idx], 1);
            }
            right++;
            cnt++;
            if (k < cnt) {
                if (ateDish.containsKey(susi[left])) {
                    if (ateDish.get(susi[left]) == 1) {
                        ateDish.remove(susi[left]);
                        susiType.remove(susi[left]);
                    } else {
                        ateDish.computeIfPresent(susi[left], (key, value) -> value - 1);
                    }
                }
                cnt--;
                left++;
            }
            answer = Math.max(answer, susiType.size());
        }

        System.out.println(answer);
    }
}

 

풀이

간단한 슬라이딩 윈도우 문제이다.

회전초밥에서 연속으로 k 접시를 먹으면 c번 초밥을 무료로 주는 것이다. 회전초밥이라는 말은 원형이라는 의미이다. 따라서 배열 끝까지 갔더라도 다시 시작 부분과 연결해서 생각해야한다. Set을 이용해 중복제거를 해서 몇 종류의 초밥을 먹는지 쉽게 계산하고, left, right 를 포인터로 이용해 어떤 구간의 초밥을 먹었는지 알아낸다. right는 앞으로 가면서 초밥을 먹는 인덱스이고, left는 초밥을 다시 뱉는(?) 인덱스이다. Map을 이용해 어떤 종류의 초밥을 몇 개 먹었는지 계산하고 특정 종류의 초밥을 0개 먹었을 땐 Set에서도 지워준다.