[JAVA]2531 회전 초밥

 📚 문제  

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

2531번: 회전 초밥

🔍 아이디어  

완탐으로 i번째 에서 연속해서 먹을 수 있는 만큼 (i+k)만큼을 모두 확인하는 방식으로 풀어도 통과합니다.

저는 슬라이딩 윈도우 방법을 이용해서 풀었습니다

 

시작 시에 해시에 초기에 k만큼의 접시와, 쿠폰을 이용해 먹은 초밥을 미리 넣어둡니다. 

저의 경우 이때 hashmap을 사용하여 먹은 스시를 셌는데 bucket을 이용한 풀이도 가능합니다.

hash를 이용하는 경우 저의 경우는  eaten.put(susi[right], eaten.getOrDefault(susi[right], 0) + 1);과 같이 사용하여 값을 갱신하는 방식으로 진행하였습니다.

bucket을 이용하는 경우는 susi[먹은 스시의 종류] ++ 을 이용하여 if(susi[먹은스시의 종류]++ == 0) 이라면 먹을 수 있는 스시의 종류를 한 개 증가시키는 방식으로 셀 수 있습니다.

 

 

이후에는 k이후로 모든 초밥을 원형으로 돕니다.

이때 앞에서 먹었던 스시를 하나를 다시 뱉어내고 이번 접시를 먹는다 라는 느낌으로 풀이하시면 됩니다(슬라이딩 윈도우)

 

여기서 주의해야 할 것은 스시가 회전하기때문에 단순히 스시 접시만큼 반복하지 않고 (스시접시 + 연속으로 먹을 수 있는 수)만큼 반복하여 배열의 마지막 쪽과 처음을 연속으로 먹는 경우를 계산해 주어야 합니다. 해당하는 반례는 아래와 같은 경우가 있습니다. 초밥 2,3을 먹고 기존의 쿠폰인 5번 초밥까지 먹어 최대 3개의 초밥을 먹을 수 있습니다. 

 

테스트 케이스 

4 30 2 5
3
5
5
2

=> 3이 나와야 합니다(원형으로 생각해야 합니다)

 

계산하는 경우는 해시이기 때문에 값이 스시의 값이 0인 경우는 해시에서 완전히 제거해 주어야 합니다.

bucket을에서는 빼는 경우 if(--bucket[]==0)인 경우 먹을 수 있는 초밥의 수를 하나 감소시키고, 버킷 if(++bucket[]==1)인 경우에는 먹을 수 있는 초밥이 하나 증가한 경우이기 때문에 먹을 수 있는 초밥의 수를 하나 증가시키는 방법으로 진행하면 될 것 같습니다.

 

📝 풀이 

package 백준.slidingWindow;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.StringTokenizer;

public class Boj_2531_회전초밥 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        int dishCnt = Integer.parseInt(st.nextToken());
        int susiCnt = Integer.parseInt(st.nextToken());
        int chainCnt = Integer.parseInt(st.nextToken());//연속해서
        int coupon = Integer.parseInt(st.nextToken());
        int max = 0;

        int[] susi = new int[dishCnt];
        for (int i = 0; i < dishCnt; i++) {
            susi[i] = Integer.parseInt(br.readLine());
        }


        HashMap<Integer, Integer> eaten = new HashMap<>();
        eaten.put(coupon, 1); //이미 먹은것
        for (int right = 0; right < chainCnt; right++) {
            eaten.put(susi[right], eaten.getOrDefault(susi[right], 0) + 1);
        }
        max = Math.max(max, eaten.size());

        //이동하면서 확인
        for (int right = chainCnt; right < dishCnt + chainCnt - 1; right++) {
            int left = susi[(right - chainCnt) % dishCnt];
            if (eaten.get(left) == 1) {
                eaten.remove(left);
            } else {
                eaten.put(left, eaten.get(left) - 1); //먹은거에서 제거
            }

            int key = susi[right % dishCnt];
            eaten.put(key, eaten.getOrDefault(key, 0) + 1);
            max = Math.max(max, eaten.size());
        }

        System.out.println(max);
    }
}