백준 15961[자바] java 회전 초밥

문제 링크: https://www.acmicpc.net/problem/15961

15961번: 회전 초밥

▶문제

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

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

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

위 할인 행사에 참여하여 가능한 한 다양한 종류의 초밥을 먹으려고 한다. 위 그림의 예를 가지고 생각해보자. k=4이고, 30번 초밥을 쿠폰으로 받았다고 가정하자. 쿠폰을 고려하지 않으면 4가지 다른 초밥을 먹을 수 있는 경우는 (9, 7, 30, 2), (30, 2, 7, 9), (2, 7, 9, 25) 세 가지 경우가 있는데, 30번 초밥을 추가로 쿠폰으로 먹을 수 있으므로 (2, 7, 9, 25)를 고르면 5가지 종류의 초밥을 먹을 수 있다. 

회전 초밥 음식점의 벨트 상태, 메뉴에 있는 초밥의 가짓수, 연속해서 먹는 접시의 개수, 쿠폰 번호가 주어졌을 때, 손님이 먹을 수 있는 초밥 가짓수의 최댓값을 구하는 프로그램을 작성하시오. 

▶입력

첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 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 이하의 정수가 각 줄마다 하나씩 주어진다. 

▶출력

주어진 회전 초밥 벨트에서 먹을 수 있는 초밥의 가짓수의 최댓값을 하나의 정수로 출력한다.

▶해설

투 포인터로 접근합니다. 조건을 살펴보겠습니다. 

 

1. 다양한 종류의 초밥을 먹은 것의 최대값

2. 연속으로 먹을 시 쿠폰을 사용할 수 있음

3. 같은 종류의 초밥이 올라가 있을 수 있음

4. 회전 초밥이므로 인덱스 0부터 끝으로도 갈 수 있음

 

투 포인터를 사용하며, 같은 종류의 초밥을 먹었을 때를 생각해줘야 합니다.

1. 처음 초밥의 개수를 저장할 initMenu배열과 먹었을 때 변한 개수를 저장할 changeMenu배열 선언 

2. 초밥을 먹었을 때는 카운터를 하면 안 되므로 먹었다는 것을 기억할 불린 check 배열 선언

 

이제 left, right를 사용합니다.

 

case 1: 초밥을 더 먹을 수 있을 때

만약 right-left <k라면 아직 더 많은 초밥을 먹을 수 있습니다. 

 

1-1. 아직 먹어보지 않은 종류의 초밥일 때

 

check 배열을 변경해줍니다. 또한 changeMenu의 값을 1 줄여줍니다. 그리고 right++ 증가시킵니다. 개수를 카운트하는 count를 1 증가시킵니다.

 

1-2. 먹어본 종류의 초밥일 때

 

changeMenu의 값만 1 감소시킵니다. 

if(right-left<k){
    if(!check[arr[right]]){
        changeMenu[arr[right]]--;
        count++;
        check[arr[right]]=true;
    }
    else{
        changeMenu[arr[right]]--;
    }
    right++;
}

 

case 2: 초밥을 더 이상 먹을 수 없을 때

 

left +1 해줘서 앞 접시를 안 먹은 상태로 만들어줘야 합니다. 먼저 changeMenu [left]의 값을 1 더해줘서 먹지 않은 상태로 만듭니다. 그 후 아래의 경우의 수를 나눠서 진행하고, left +1을 해줍니다. 

 

2-1. changeMenu [left]==initMenu [left] 

 

left의 초밥은 더 이상 먹은 종류가 아니므로 check [left]를 false로 바꿔주고, 먹어본 종류의 개수 count를 1 줄여줍니다. 

 

2-2. changeMenu [left]!=initMenu [left] 

 

left의 초밥의 먹은 개수는 줄었지만, 아직도 left 초밥은 먹은 상태입니다. 따라서 count의 변화는 없습니다. 

 

if(!check[c]){
    result = Math.max(result, count+1);
}
changeMenu[arr[left]]++;
if(changeMenu[arr[left]]==initMenu[arr[left]]){
    check[arr[left]]=false;
    count--;
}
left++;

 

위의 모든 과정을 마쳤다면, 최종적으로 쿠폰의 초밥의 종류를 이미 먹었을 때와 먹어보지 않았을 때의 경우의 수로 나누고, 최댓값을 구해줍니다. 

if(!check[c]){
    result = Math.max(result, count+1);
}else {
    result = Math.max(result,count);
}

 

한 가지 조심해야 할 점은 조건을 살펴볼 때 적은 4 번째 조건입니다. 회전 초밥이므로 0-> n->n-1-> n-2 방향으로도 섭취할 수 있습니다. 따라서 배열의 길이를 n이 아닌 n+k로 선언해주고, arr 뒤의 k-1만큼의 arr 앞부분을 뒤에 붙여줘야 합니다. 

for(int i=n+1; i<n+k; i++){
    arr[i] = arr[i-n];
}

 

따라서 투 포인터를 끝낼 때는 아래와 같습니다. 

if(right==n+k){
    break;
}

 

전체 코드

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


public class Main {

    static int [] initMenu;
    static int [] changeMenu;
    static int [] arr;
    static int result;
    static boolean[] check;
    static int n,d,k,c;
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] s = br.readLine().split(" ");

        n = Integer.parseInt(s[0]);
        d = Integer.parseInt(s[1]);
        k = Integer.parseInt(s[2]);
        c = Integer.parseInt(s[3]);

        arr = new int[n+k];
        initMenu = new int[d+1];
        changeMenu = new int[d+1];
        check = new boolean[d+1];
        for(int i=1; i<=n; i++){
            arr[i] = Integer.parseInt(br.readLine());
            initMenu[arr[i]]++;
            changeMenu[arr[i]]++;
        }

        changeMenu[c]++;

        for(int i=n+1; i<n+k; i++){
            arr[i] = arr[i-n];
        }

        solve();
        System.out.println(result);
    }
    private static void solve(){
        int left= 1;
        int right = 1;
        int count = 0;
        while(left<=right){
            if(right-left<k){
                if(!check[arr[right]]){
                    changeMenu[arr[right]]--;
                    count++;
                    check[arr[right]]=true;
                }
                else{
                    changeMenu[arr[right]]--;
                }
                right++;
            }
            else{
                changeMenu[arr[left]]++;
                if(changeMenu[arr[left]]==initMenu[arr[left]]){
                    check[arr[left]]=false;
                    count--;
                }
                left++;
            }
            if(!check[c]){
                result = Math.max(result, count+1);
            }else {
                result = Math.max(result,count);
            }
            if(right==n+k){
                break;
            }
        }
    }
}