[BOJ 백준] 2531번 회전초밥 (Java)

주어진 회전 초밥 벨트에서 먹을 수 있는 초밥의 가짓수의 최댓값을 하나의 정수로 출력한다.

2531번: 회전 초밥

처음에는 List와 Set을 사용해서 풀었지만, 매번 N이 최대 30,000, k가 최대 3,000이기 때문에 시간초과가 났습니다.

 

해결 방법

1. 슬라이딩 윈도우

크기가 d인 selected라는 정수 배열을 이용합니다.

현재 선택된 초밥의 번호를 인덱스로 하여 개수를 늘립니다.

초기 세팅을 한 후 0부터 N까지 탐색하면서, 윈도우에서 제외된 값과 추가된 값에 대한 연산을 진행합니다.

그러나 이 아이디어만 도입한다면 또 "틀렸습니다"를 마주하게 되는데요..

2. 원형 테이블

회전 초밥은 원형 테이블이 계속 회전한다는 것을 유의해야 합니다.

따라서 초밥 배열을 N이 아닌 N + k로 세팅해주어야 모든 경우의 수를 탐색할 수 있습니다.

 

간단해 보이지만 두 가지 아이디어를 떠올리기 쉽지 않았습니다...

특히 원형이라는 조건을 놓치게 되면 주어진 테스트 케이스만으로는 알아내기 쉽지 않아, 반례 찾는 연습을 필히 해야할 것 같습니다…

 

Java 코드

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

public class Main {

    static int solution(int N, int d, int k, int c, int[] sushi) {
        int cnt = 1;
        int[] selected = new int[d + 1];
        selected[c]++;
        for (int i = 0; i < k; i++) {
            if (selected[sushi[i]] == 0) cnt++;
            selected[sushi[i]]++;
            sushi[N + i] = sushi[i];
        }

        int answer = cnt;

        for (int i = 0; i < N; i++) {
            selected[sushi[i]]--;
            if (selected[sushi[i]] == 0) cnt--;
            if (selected[sushi[i + k]] == 0) cnt++;
            selected[sushi[i + k]]++;

            answer = Math.max(answer, cnt);
        }

        return answer;
    }

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

        System.out.println(solution(N, d, k, c, sushi));
        br.close();
    }
}