[BOJ/Java] 2531. 회전 초밥

[BOJ/Java] 2531. 회전 초밥

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

---

문제 해석

회전 초밥 문제는 주어진 회전 초밥 벨트에서 연속된 K개의 초밥을 선택했을 때, 이때의 다양한 초밥의 종류를 최대화하는 문제이다. 또한, 초밥의 선택은 하나의 쿠폰을 이용하여 원하는 초밥 한 종류를 추가할 수 있어, 이를 고려한 최적의 초밥 선택 전략을 요구한다.

풀이 과정

 

1. 초기 설정: 입력을 받아 전역 변수로 N(총 초밥의 개수), D(초밥의 종류 수), K(연속해서 먹을 초밥의 개수), C(쿠폰으로 먹을 수 있는 초밥 번호)를 설정하고, 초밥의 번호를 저장할 배열 arr을 선언한다.
2. 슬라이딩 윈도우 및 초밥 종류 카운팅: 첫 K개의 초밥을 선택하여 종류를 카운팅한다. 이를 기반으로 슬라이딩 윈도우 기법을 사용해 한 칸씩 움직이면서 초밥을 추가하고 제거하면서 최대 종류 수를 갱신한다.
3. 쿠폰 사용 고려: 각 윈도우에서 쿠폰에 해당하는 초밥이 없으면 쿠폰을 사용해 한 종류를 추가할 수 있으므로 종류 수를 +1 하여 계산한다.
4. 최대 종류의 수 갱신: 모든 윈도우를 순회하며 최대 초밥 종류 수를 갱신한다.

코드

package edu.ssafy.im.BOJ.Silver.S1.No2531;

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

public class Main {
    private static int N, D, K, C;
    private static int[] arr;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        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());
        
        arr = new int[N];
        for (int n = 0; n < N; n++) {
            arr[n] = Integer.parseInt(br.readLine());
        }

        // 해결 방법 실행 및 결과 출력
        sb.append(sol());
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    private static int sol() {
        int ans = 0, count = 0;
        int[] check = new int[D+1]; // 초밥 종류 카운팅 배열

        // 초기 K개 초밥 카운팅
        for (int k = 0; k < K; k++) {
            if (check[arr[k]] == 0) count++;
            check[arr[k]]++;
        }

        // 슬라이딩 윈도우
        for (int n = 0; n < N; n++) {
            // 쿠폰 초밥 추가 체크
            if (check[C] == 0) ans = Math.max(ans, count+1);
            else ans = Math.max(ans, count);

            // 첫 번째 초밥 제거 및 마지막 초밥 추가
            check[arr[n]]--;
            if(check[arr[n]] == 0) count--;
            if(check[arr[(n+K)%N]] == 0) count++;
            check[arr[(n+K)%N]]++;
        }

        return ans; // 최대 종류 수 반환
    }
}

시간 복잡도 분석

시간 복잡도는 O(N), 이는 초밥의 총 개수 N에 대해 각 초밥을 한 번씩만 처리하기 때문이다. 각 윈도우의 슬라이드 시에 상수 시간 내의 작업만 수행되므로 전체적인 계산 효율은 매우 우수하다.

느낀점

이 문제는 슬라이딩 윈도우 기법을 통해 연속된 데이터의 범위 내 최적화 문제를 해결하는 좋은 예시다. 쿠폰을 사용하는 추가 조건을 효과적으로 처리하는 방법을 고안하는 것이 핵심적인 도전이었다. 이를 통해 문제를 효율적으로 해결할 수 있었다는 점에서 만족스럽다.