[BOJ-15961] 회전 초밥(JAVA)

백준 15961 회전 초밥

 

15961번: 회전 초밥

 

문제 설명

 

 - 회전 초밥 음식점에는 회전하는 벨트 위에 여러 가지 종류의 초밥이 접시에 담겨 있다.

 

 - 초밥 음식점은 두 가지 행사를 통해서 매상을 올리려 한다.

   1. 벨트의 임의의 한 위치부터 k개 접시를 연속으로 먹을 경우 할인된 정액 가격으로 제공한다.

   2. 각 고객에게 초밥의 종류 하나가 쓰인 쿠폰을 발행하고, 이 쿠폰에 적혀진 종류의 초밥 하나를 무료로 제공한다.

      이 초밥이 벨트 위에 없는 경우, 요리사가 새로 만들어 손님에게 제공한다.

 

 - 메뉴에 있는 초밥의 가짓수, 연속해서 먹는 접시의 개수, 쿠폰 번호가 주어졌을 때

   손님이 먹을 수 있는 초밥 가짓수의 최댓값을 구하라.

---

 

입력 값

 

 - 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 주어진다.

   ( 2 <= N <= 3,000,000 / 2 <= d <= 3,000 / 2 <= k <= 3,000(k <= N) / 1 <= c <= d )

 

 - 두 번째 줄부터 N개의 줄에는 벨트의 한 위치부터 시작하여 회전 방향을 따라갈 때

   초밥의 종류를 나타내는 1이상 d이하의 정수가 각 줄마다 하나씩 주어진다.

 

---

 

 

예제

---

 

 

문제 분석

 

 - 이 문제는 주어진 크기만큼 초밥을 획득 했을 때, 가장 많은 가짓수를 구하는 문제이다.

 

 - 즉, 이 문제는 크기가 주어졌기 떄문에 슬라이딩 윈도우를 이용하면 간단하게 풀 수 있다.

투 포인터, 슬라이딩 윈도우 기법

 

 - 슬라이딩 윈도우를 점점 이동해가면서, 초밥의 종류를 알아본다.

 

 - 슬라이딩 윈도우를 움직일 때마다 개수를 세면 시간 초과가 발생하기 떄문에 추가, 삭제된 개수만 세면 된다.

 

 

 

 

---

 

 

소스 코드

 

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(bf.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 boards[] = new int[N+k];

        int selected[] = new int[d+1];

        for(int i=0;i<N;i++){
            int n = Integer.parseInt(bf.readLine());
            boards[i]=n;
        }

        int result=1;

        selected[c]++;
        for(int i=N;i<N+k;i++){
            boards[i]=boards[i-N];
            if(selected[boards[i]]==0){
                result++;
            }
            selected[boards[i]]++;

        }

        int nowSum=result;

        for(int i=k;i<N+k;i++){

            int deleteNum = boards[i-k];
            selected[deleteNum]--;
            
            // 빼야 하는 초밥이 모두 빠진 경우
            if(selected[deleteNum]==0){
                nowSum--;
            }

            int addNum = boards[i];
            selected[addNum]++;

            // 새로 들어온 경우
            if(selected[addNum]==1){
                nowSum++;
            }

            result = Integer.max(result,nowSum);
        }
        System.out.println(result);


    }
}