2531번 문제

문제

슬라이딩 윈도우를 사용하는 문제이다.

풀이

기본 로직

• int[d+1] sushi : 벨트 위에 올려진 초밥들
• int[N] selected : 각 초밥 종류별로 선택된 수

1. 쿠폰으로 주어지는 초밥은 이미 먹었다고 가정한다.
2. 벨트의 0번째 위치부터 시작해서, 연속해서 먹는 k만큼 범위를 옮겨가며 cnt를 늘리고 줄인다.
3. 가장 큰 cnt를 max에 저장한다.

그렇게 어렵지 않게 구현을 했다고 생각했다.
문제와 함께 주어진 예제 입력에 출력도 모두 맞게 나왔다.
근데도 제출을 하면 자꾸만 실패가 떴고 ... 틀린 로직이 없는 것 같았는데 답답해서 죽을 뻔 했다. 결국 실패한 채로 며칠 뒤 다시 문제를 봤는데 ... 유레카 ... '회전' 초밥인 것을 전혀 생각하지 못 하고 있었다.

문제 이해 부족

계속해서 실패를 받은 이유는 단순했다.
초밥 벨트가 '회전' 한다는 점을 간과하고 있었다 ㅠ
만일, 접시의 수가 8개고 k가 4인 예제를 예로 들면,
나는 sushi[0~3]의 범위부터 sushi[5~8]의 범위만 커버하고 있었던 거다.
sushi[8]-sushi[0]-sushi[1]-sushi[2] 의 범위도 생각해야 하는 것을 ..

이를 깨닫고 나머지 연산을 이용하여 로직을 바꿔 구현하였고, 바로 통과하였다.

하 2시간은 넘게 어떤 로직이 틀렸을까 고민했었는데 .... 아예 문제 자체를 잘못 이해했었다니

최종 제출 코드

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

public class Main {
    public static void main(String[] args) throws Exception{
        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[] selected = new int[d+1];
        int[] sushi = new int[N];
        for(int i = 0; i < N; i++) {
            sushi[i] = Integer.parseInt(br.readLine());
        }

        // 쿠폰 초밥은 이미 먹었다고 가정
        selected[c] = 1;
        int cnt = 1;
        int max = 1;

        // 0~k-1까지 기본 초기화
        for(int i = 0; i<k; i++) {
            if(selected[sushi[i]] == 0) { // 
                cnt++;
            }
            selected[sushi[i]]++;
        }

        max = cnt;
        for(int i = 1; i<N; i++) { 
            // 현재 위치 i -> 범위의 첫 번째 위치가 됨
            // (i+k-1) % M -> 범위의 마지막 위치가 됨 (추가되는 위치)
            selected[sushi[i-1]]--;
            if(selected[sushi[i-1]] == 0) cnt--;
            selected[sushi[(i+k-1)%N]]++;
            if(selected[sushi[(i+k-1)%N]] == 1) cnt++;
            if(max < cnt) max = cnt;
        }

        System.out.println(max);
    }
}