백준 - 2531

백준 2531 회전초밥

문제

회전 초밥 음식점에는 회전하는 벨트 위에 여러 가지 종류의 초밥이 접시에 담겨 놓여 있고, 손님은 이 중에서 자기가 좋아하는 초밥을 골라서 먹는다. 초밥의 종류를 번호로 표현할 때, 다음 그림은 회전 초밥 음식점의 벨트 상태의 예를 보여주고 있다. 벨트 위에는 같은 종류의 초밥이 둘 이상 있을 수 있다.

새로 문을 연 회전 초밥 음식점이 불경기로 영업이 어려워서, 다음과 같이 두 가지 행사를 통해서 매상을 올리고자 한다.

원래 회전 초밥은 손님이 마음대로 초밥을 고르고, 먹은 초밥만큼 식대를 계산하지만, 벨트의 임의의 한 위치부터 k개의 접시를 연속해서 먹을 경우 할인된 정액 가격으로 제공한다.
각 고객에게 초밥의 종류 하나가 쓰인 쿠폰을 발행하고, 1번 행사에 참가할 경우 이 쿠폰에 적혀진 종류의 초밥 하나를 추가로 무료로 제공한다. 만약 이 번호에 적혀진 초밥이 현재 벨트 위에 없을 경우, 요리사가 새로 만들어 손님에게 제공한다.

풀이

최대한 많은 종류의 초밥을 먹는 것과 두 개의 포인터가 같은 간격으로 원형 형태의 배열을 탐색하는 것이 중요한 점

k의 값이 4인 예시
(9, 7, 30, 2), (30, 2, 7, 9), (2, 7, 9, 25)
중 쿠폰 값 c가 30인 경우 30이 없는 경우 (2, 7, 9, 25)+30 이 5가지로 정답이 된다.

투 포인터가 진행되는 방식은 이전의 스타트 포인터를 제거하고, 엔드 포인터를 다음 칸으로 옮긴다.
배열을 만들어 스타트 포인터의 인덱스에 -1을 하고,
엔드 포인터 인덱스에 +1을 한다.
먹은 초밥의 인덱스에 c 값이 없다면 출력값에 +1을 한다.

코드

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

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[] sushiOnTable = new int[N]; // 접시에 올려진 초밥 번호 배열
        for(int i=0;i<N;i++){
            sushiOnTable[i] = Integer.parseInt(br.readLine());
        }
        int[] sushi = new int[d+1]; //1~d까지 초밥 번호 배열 최대한 많은 종류를 먹기가 목표
        int count = 0; //현재 값
        int max = 0; //최대값
        for(int i=0;i<k;i++){
            int a = sushiOnTable[i];
            if(sushi[a]==0){// 새롭게 먹게되는 초밥인지 필터링
                count++; 
            }
            sushi[a]++;
        }
        max = count;
        
        for(int i=0;i<N;i++){ 
            int start = i;
            int end = (i+k)%N;
            if(count >= max){
                if(sushi[c]==0){ //쿠폰 번호 초밥을 먹지않았을 경우
                    max = count+1;
                }else{
                    max = count;
                }
            }
            //탐색 과정
            sushi[sushiOnTable[start]]--;  //시작 포인터 인덱스 -1
            if(sushi[sushiOnTable[start]]==0){count--;} 
            if(sushi[sushiOnTable[end]]==0){count++;} 
            //먹고 있는 초밥 업데이트
            
            sushi[sushiOnTable[end]]++; //끝 포인터 인덱스 +1
        }
        System.out.println(max);
    }
}