[BOJ] 2531번 회전 초밥 - JAVA

💡 문제

💬 입출력 예시

📌 풀이(소스코드)

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

public class Main {
    static int N, D, K, C, maxCnt, cnt;
    static int[] belt, sushi;

    public static void main(String[] args) throws IOException {
        init();
        // 1. 처음부터 k개 만큼 먹었을 때의 초기화
        initCnt();
        // 2. 1번부터 n-1 번까지 start 만 이동 시킬경우 K 는 고정
        process();
        print();
    }

    private static void init() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        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()) - 1;

        belt = new int[N];
        sushi = new int[D];
        for (int i = 0; i < N; i++) {
            belt[i] = Integer.parseInt(br.readLine()) - 1;
        }
    }

    private static void initCnt() {
        for (int i = 0; i < K; i++) {
            if (sushi[belt[i]] == 0) {
                cnt++;
            }
            sushi[belt[i]]++;
        }
    }

    private static void process() {
        for (int start = 0; start < N; start++) {
            updateMax();
            moveEndPointer(start);
            moveStartPointer(start);
        }
    }

    private static void updateMax() {
        if (maxCnt <= cnt) {
            if (sushi[C] == 0) {
                maxCnt = cnt + 1;
            } else {
                maxCnt = cnt;
            }
        }
    }

    private static void moveEndPointer(int start) {
        int end = (start + K) % N;
        if (sushi[belt[end]] == 0) {
            cnt++;
        }
        sushi[belt[end]]++;
    }

    private static void moveStartPointer(int start) {
        sushi[belt[start]]--;
        if (sushi[belt[start]] == 0) {
            cnt--;
        }
    }

    private static void print() {
        System.out.println(maxCnt);
    }
}

📄 해설

접근

• 투 포인터/슬라이딩 윈도우 알고리즘을 사용하여 해결하는 문제이다.
• 해당 알고리즘에 대한 이해가 부족한 듯. 한 세번째 푸는 문제인데 계속 틀린다

과정

• 시작부터 K 개 만큼의 접시를 먹었을 때의 cnt 값을 초기화를 해준다.
• 이후 첫번째 접시부터 N 번째 접시까지 반복해서 아래 작업을 수행한다.
  • 최댓값을 갱신해준다. 이때, 쿠폰 번호의 초밥은 무조건 먹은 상태여야하므로, 이를 생각해서 갱신해준다.
  • end 포인터를 이동시킨다. 이때, 해당 위치의 초밥이 먹지 않은 종류의 초밥이면 cnt 값을 증가시킨다.
    • 회전 초밥이므로, end 포인터 계산 시에는 나머지 연산을 사용해 계산해준다.
  • start 포인터를 이동시킨다. 이때, 해당 위치의 초밥 종류 한개를 먹지 않은 상태로 변경하고, 해당 종류 초밥을 아예 먹지 않은 상황이 될 경우 cnt 값을 감소 시킨다.
• 위 과정을 반복하면 정답이 구해진다.