[백준] BOJ 2531 회전 초밥 (실버 1)

문제

---

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

2531: 회전 초밥

---

해설

---

1. 연속으로 k개를 선택해야 하기 때문에 슬라이딩 윈도우를 사용하여 왼쪽에서 하나 삭제, 오른쪽에 하나 추가 하는 방식으로 구현한다.
2. 이를 Set을 사용하여 중복으로 들어가지 않도록 해준다.
   • 이때, 주의해야할 점은 (7, 9, 7, 10)이라는 순서로 초밥을 선택한 경우 Set에는 (7, 9, 10)만 들어있다.
     
     
   • 왼쪽 7을 삭제하면 Set은 중복된 값이 들어가지 않기 때문에
     (7, 10)이 되어 오른쪽에 11을 추가해도 (9, 10, 11)이 되어 중간에 있는 7이 사라지게 된다.
     
     
   • 따라서, 현재 Set에 어떤 수가 몇개 들어있는지를 관리해주는 counts라는 Map을 사용한다.
     
     
   • 이를 통해 삭제하려는 수가 왼쪽 수 하나일 때만 Set에서 삭제하도록 한다. (오른쪽 추가도 동일하게 고려해야함.)
3. 이렇게 슬라이딩 윈도우를 한칸 밀었을 때 Set의 사이즈와
   해당 Set안에 쿠폰으로 받는 초밥의 번호가 존재하지 않으면 개수를 + 1 해준다.
4. 최종적으로 가장 많은 종류를 먹는 경우의 종류를 출력한다.

---

코드 (슬라이딩 윈도우)

---

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

public class BOJ2531 {
    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[] sushis = new int[N];
        for (int i = 0; i < N; i++) {
            sushis[i] = Integer.parseInt(br.readLine());
        }

        Map<Integer, Integer> counts = new HashMap<>();
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < k; i++) {
            if(set.add(sushis[i])) {
                counts.put(sushis[i], 1);
                continue;
            }
            Integer count = counts.get(sushis[i]);
            counts.put(sushis[i], count + 1);
        }

        //슬라이딩 윈도우
        int size = set.size();
        int max = set.contains(c) ? size : size + 1;
        int left = 0;
        for (int right = k; right < N + k - 1; right++) { //순환 구조의 마지막 -> 마지막 원소 1개 + 시작 ~ d - 1개
            if(counts.get(sushis[left % N]) == 1) {
                set.remove(sushis[left % N]);
            }
            counts.put(sushis[left % N], counts.get(sushis[left % N]) - 1);

            if(counts.getOrDefault(sushis[right % N], 0) == 0){
                set.add(sushis[right % N]);
            };
            counts.put(sushis[right % N], counts.getOrDefault(sushis[right % N], 0) + 1);

            size = set.contains(c) ? set.size() : set.size() + 1;
            max = Math.max(max, size);
            left++;
        }
        System.out.println(max);
    }
}

---

결론

---

슬라이딩 윈도우를 제대로 사용해서 해결해본 문제!

슬라이딩 윈도우의 핵심은 미는 만큼만 갱신하는 것 같다. (바뀌는 부분만?)

---