[백준] 15961 회전 초밥 - Java

 

 

 

문제 출저

https://www.acmicpc.net/problem/15961

15961번: 회전 초밥

 

 

 

문제 풀이

회전 초밥의 가짓수와 순서가 주어집니다. 이 때 연속한 k개의 초밥 + 이벤트 초밥을 더했을 때 최대한 다양하게 먹은 초밥의 가짓수를 구하는 것이 이 문제의 요구사항입니다. 

 

int[] board = new int[n+k] 를 선언합니다. 일차원 정수 배열 board는 초밥의 순서는 담는다. 이 때, 회전 초밥이므로 끝은 처음과 이어진다. 따라서 +k를 더하여 끝과 처음이 이어지게 하였습니다. 

int[] count = new int[d+1] 를 선언합니다. 일차원 정수 배열 count는 손님이 고른 초밥 당 갯수를 나타냅니다.

Set<Integer> select = new HashSet<>() 을 선언합니다. 이 Set은 k개를 골랐을 때 중복을 없애서 총 가짓수를 편하게 구할 수 있습니다.

 

이벤트 초밥은 언제든 주문할 수 있습니다.

탐색하면서 나올 수 있는 최대의 수는 k개 입니다.

따라서 select에 이벤트 초밥을 번호를 넣으면서 이벤트 초밥의 count는 k+1을 하였습니다.

이로 인해 이벤트 초밥은 select에 영구히 남아있게 했습니다. 

 

맨 처음 0 ~ k 개를 담습니다.

담긴 초밥 번호에 해당하는 count 번호를 올리고 select 에 추가합니다.

 

board를 탐색합니다.

새로 들어온 초밥은 count 번호를 올리고 select에 추가합니다. 

탐색에 따라 맨 처음 들어온 초밥은 나가게 되므로 count 번호를 낮춥니다. 이 때 count 번호가 0이 되면 select에서 제외했습니다. 

한 칸 탐색할 때 마다 answer = Math.max(answer, select.size()); 를 통해 answer에 최댓값을 저장하게 했습니다. 

 

 

 

소스 코드

package baekjoon.backjoon9.day22;

/*

회전 초밥
https://www.acmicpc.net/problem/15961

 */

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

public class B15961 {

    static int n, d, k, c;
    static int[] board;

    static Set<Integer> select;

    static int[] count;

    static int answer;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        d = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());

        board = new int[n + k];
        for(int i = 0; i < n; i++) {
            board[i] = Integer.parseInt(br.readLine());
        }

        for(int i = 0; i < k; i++) {
            board[n+i] = board[i];
        }

        count = new int[d+1];
        select = new HashSet<>();
        select.add(c);
        count[c] = k+1;

        answer = select.size();



        for(int i = 0; i < k; i++) {
            select.add(board[i]);
            count[board[i]]++;
        }

        answer = select.size();

        for(int i = k; i < n+k; i++) {
            select.add(board[i]);
            count[board[i]]++;

            if(board[i-k] != c) {
                count[board[i-k]]--;
                if(count[board[i-k]] == 0) {
                    select.remove(board[i-k]);
                }
            }

            answer = Math.max(answer, select.size());

        }

        System.out.println(answer);

    }

}