[JAVA]BOJ 15961, 회전 초밥

16472, 고냥이 문제와 비슷하다. 거의 똑같다!

 

1. 배열에 입력한 초밥 저장한다.

2. k개의 초밥이 있는 윈도우를 만들고 left와 right를 증가시켜 윈도우를 움직인다.

3. 윈도우 안에 초밥을 map형식으로 저장하고 map의 크기와 max를 비교해 max를 찾는다.

주의할 점은 쿠폰초밥(c)를 처음에 추가해준다. 무조건 k개의 초밥을 먹고 쿠폰초밥(c)를 먹기때문에 처음부터 쿠폰초밥(c)를 map에 추가했다.

 

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

public class BOJ15961 {
    public static int getMaxSushi(int[] sushi, int N, int k, int c){
        Map<Integer, Integer> sushiMap = new HashMap<>();
        int left = 0, right = 0, max = 0;

        // 서비스 초밥 먼저 추가
        sushiMap.put(c, 1);

        // 처음 window 설정
        while(right < k){
            sushiMap.put(sushi[right], sushiMap.getOrDefault(sushi[right], 0) + 1);
            right++;
        }
        right--;
        
        while(left < N){
            max = Math.max(max, sushiMap.size()); // 개수 구하기

            right++;
            if(right >= N) // index가 넘어가면 0으로 돌아가야함
                right -= N;

            sushiMap.put(sushi[right], sushiMap.getOrDefault(sushi[right], 0) + 1); // 우측 초밥 하나 늘리기
            sushiMap.put(sushi[left], sushiMap.get(sushi[left]) - 1); // 좌측 초밥 하나 줄이기
            if(sushiMap.get(sushi[left]) == 0)
                sushiMap.remove(sushi[left]);
            left++;
        }
        return max;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N, d, k, c, i;
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        d = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());
        int[] sushi = new int[N];

        for(i=0;i<N;i++)
            sushi[i] = Integer.parseInt(br.readLine());

        System.out.println(getMaxSushi(sushi, N, k, c));

    }
}