오늘의 1솔 ♬

오늘의 문제는 백준의 Silver 1 회전초밥 !
바로 풀고 싶다면 요기로 → 문제 바로가기

문제 설명

1. 손님은 초밥 종류가 하나 쓰여진 쿠폰을 받는다
2. 회전 초밥 벨트에서 연속으로 K개의 접시를 먹으면 1번에서 받은 쿠폰의 초밥 종류를 하나 무료르 받는다
3. 손님은 최대한 다양한 종류의 초밥을 먹고 싶다
4. 회전 초밥 벨트의 상태가 주어질 때, 손님이 먹을 수 있는 초밥의 최대 가짓수를 구해라

풀이

접근 방법

1. sushiBelt(회전 초밥 벨트에 놓인 초밥 번호) , sushiCount(인덱스: 초밥 번호, 값: 해당 초밥이 포함된 개수) 배열을 만든다
2. 1번부터 K번 칸까지 아래 과정을 반복한다
   2-1. 해당 칸의 초밥 번호가 아직 포함되지 않은 것이라면 count(초밥의 가짓수) 를 증가시킨다
   2-2. 해당 칸의 sushiCount 를 1 증가시킨다
3. 만약 C(쿠폰 초밥 번호) 번째 칸의 sushiCount 가 0이라면 현재 조합에 C번 초밥이 포함되지 않은 것이므로 가짓수가 하나 추가되어 count+1 을, 반대 경우면 그대로 count 를 answer 에 저장한다
4. 1번 칸부터 N-1번 칸까지 아래 과정을 반복한다
   4-1. first(조합에서 빠질 초밥 번호) , last(조합에 추가될 초밥 번호) 를 구한다
   4-2. first 칸의 sushiCount 를 1 감소, last 칸의 sushiCount 를 1 증가시킨다
   4-3. first 칸의 sushiCount 가 0이면 count 를 1 감소, last 칸의 sushiCount 가 1이면 count 를 1 증가시킨다
   4-4. 기존 answer 와 count(C번째 칸이 0이라면 count+1) 중 최대값을 갱신한다

슬라이딩 윈도우

전형적인 슬라이딩 윈도우 문제다
슬라이딩 윈도우란, 고정된 크기(이 문제에서는 K)가 주어지고 그만한 윈도우를 만들어 슬라이드 하는 것이다
첫 윈도우에 대한 값은 따로 구하고, 그 다음 거기서 양 끝의 값이 하나씩 빠지고 추가되는 형식으로 진행이 된다
연속된 배열에 대한 연산이 필요할 때, 양 끝만 값이 변하고 중간은 같다면 매번 새로 구할 필요가 없기 때문에 사용한다
그림으로 보면 훨씬 이해가 쉽다

고정된 크기(5)가 윈도우다
1번부터 5번까지, 2번부터 6번까지, ..., 12번부터 4번까지!
크기 5의 연속된 배열만큼에 대해 합을 구해야 한다고 생각해보자

1번부터 5번까지, 2번부터 6번까지의 윈도우다
그런데 연속되어 있다는 특성 때문에 뭔가 규칙이 보인다

이전 윈도우에서 맨 앞을 빼고, 새 윈도우의 마지막을 추가해주면 가운데 값은 그대로 사용할 수 있다
즉, 윈도우를 매번 새로 구하는 것이 아니라, 앞과 뒤에서 연산해준다면 매우 간단하게 연산이 가능하다

그래서 최종적으로 윈도우들의 흐름을 보게 되면 이렇게 미끄러지는 듯한 모습이다
슬라이딩 윈도우!
좋아하는 알고리즘 중에 하나이다

코드

package a2408;

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

public class d13_bj_s1_2531_회전_초밥 {
    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[] sushiBelt = new int[N];
        int[] sushiCount = new int[D+1];
        
        int answer = 0;
        int count = 0;
        
        for(int i=0; i<N; i++){
            sushiBelt[i] = Integer.parseInt(br.readLine());
        }
        
        for(int i=0; i<K; i++){
            int sushi = sushiBelt[i];
            if(sushiCount[sushi]++ == 0){ count++; }
        }
        answer = sushiCount[C] == 0? count + 1: count;
        
        for(int i=0; i<N-1; i++){
            int first = sushiBelt[i];
            int last = sushiBelt[(i+K)%N];
            if(--sushiCount[first] == 0){ count--; }
            if(sushiCount[last]++ == 0){ count++; }
            answer = Math.max(answer, sushiCount[C] == 0? count + 1: count);
        }
        
        System.out.println(answer);
    }
}

마무리

나에게는 초밥 알레르기가 있다