[JAVA]백준 2531: 회전초밥

백준 2531: 회전초밥

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

풀이

• Queue, 중복 처리가 핵심이라고 생각한다.
• ‘회전’ 초밥이기 때문에 리스트를 순회하되 뒷쪽 초밥으로 시작하는 경우 처음 인덱스 초밥들도 먹어야 한다.
  • 이는 순회를 N+k번 인덱스까지 하고 인덱스 접근을 나머지 연산으로 함으로써 해결
• 초밥을 먹는 것은 Queue, HashMap을 사용
  • Queue: 현재 먹는 초밥
  • HashMap: 초밥의 번호와 먹은 개수를 저장함으로써 같은 초밥이 여러번 카운트되지 않도록 함. 1. 초밥 리스트를 순회하며 Queue에 초밥을 넣는다. 또한 Map에 같은 초밥이 있다면 개수를 더하고 없다면 새로 추가한다. 2. Queue의 크기가 k보다 크다면 poll을 통해 가장 먼저 먹은 초밥의 개수를 줄인다. 0이라면 없앤다. 3. Queue 안에 쿠폰에 해당하는 c가 존재한다면 현재 Queue의 크기(먹은 초밥 종류)만큼 카운트, 없다면 쿠폰으로 증정해야 하므로 +1 4. 최댓값을 구해 출력한다.

package algorithm2024.sep.day13;

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

public class BOJ_2531_회전초밥 {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws Exception {
        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());
        
        // 초밥 저장할 배열
        ArrayList<Integer> list = new ArrayList<>();

        for(int i =0 ;i<N;i++){
            list.add(Integer.parseInt(br.readLine()));
        }

        Queue<Integer> q = new LinkedList<>();
        HashMap<Integer, Integer> map = new HashMap<>();

        int max = 0;

        // 회전초밥이므로 리스트의 끝까지만 탐색하는 것이 아닌 k개를 추가로 탐색하면서 추가함.
        // 다음에 올 초밥을 추가하고 존재하는 초밥들을 Map에 저장하고 Map의 크기를 계산함으로써 중복된 초밥을 하나로 계산 
        for(int i =0;i<N+k;i++){
            int newSushi = list.get(i%N);
            q.add(newSushi);
            map.put(newSushi, map.getOrDefault(newSushi, 0)+1);
            if(q.size()>k){
                int pollSushi = q.poll();
                if(map.get(pollSushi)>1){
                    map.put(pollSushi, map.get(pollSushi)-1);
                }else{
                    map.remove(pollSushi);
                }
            }
            int cnt = map.containsKey(c)?map.size():map.size()+1;
            max = Math.max(cnt, max);
        }
        System.out.println(max);

    }

}

---

Issue

• 중복 처리를 안하고 먹는다면 같은 초밥을 여러번 카운트 할 수 있으니 주의하자.