[백준] 15961: 회전 초밥 - JAVA

18 Jul 2023 in Algorithm on 기타

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

풀이

슬라이딩 윈도우를 사용해서 카운트하는 문제였다.

회전 초밥을 연속에서 k개 먹어야하는데 최대한 다양한 종류를 먹으려고 한다.

쿠폰이 하나 주어지고 쿠폰에 적혀진 종류의 초밥을 먹지 않았으면 하나 제공해 준다.

즉, 가장 다양하게 먹으려면 연속된 k개에서 다 다른 초밥을 먹고 쿠폰에 있는 초밥을 제공받아 먹어야 한다.

int로 먹은 것을 체크하는 배열을 만들었다.

left는 0, right는 k-1부터 시작하여 1씩 늘리면서 체크해준다.

체크 배열에 쿠폰에 있는 초밥이 없으면 bonus를 1로 해주고 cnt + bonus의 최댓값이 정답이 된다.

---

메모리: 170972KB

시간: 548ms

언어: Java 11

코드

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

public class Main {

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

        int[] check = new int[d + 1];
        int cnt = 0;
        int bonus = 0;
        for (int i = 0; i < k; i++) {
            if (check[sushi[i]]++ == 0) {
                cnt++;
            }
        }
        bonus = check[c] == 0 ? 1 : 0;

        int ans = cnt + bonus;
        int left = 0;
        int right = k - 1;
        while (left < N) {
            if (--check[sushi[left]] == 0) {
                cnt--;
            }
            left++;

            right++;
            if (++check[sushi[right % N]] == 1) {
                cnt++;
            }

            bonus = check[c] == 0 ? 1 : 0;

            ans = Math.max(ans, cnt + bonus);
        }

        System.out.println(ans);
    }

}