백준 2531 - 회전 초밥

Java

2531 번 - 회전 초밥

문제

1. 임의의 한 위치부터 k개 접시를 연속하여 먹는다.
2. 보너스로 하나의 스시(c)를 제공한다.

가능한 한 다양한 종류의 초밥을 먹으려고 한다.

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

2 ≤ N ≤ 30,000, 2 ≤ d ≤ 3,000, 2 ≤ k ≤ 3,000 (k ≤ N), 1 ≤ c ≤ d

접근 방법

스시의 순서대로 0부터 n-1까지 탐색하여, k개의 스시를 매번 탐색해 종류의 세는 방식으로 해결하면, O(n^2)의 시간으로 시간초과이다.

따라서, Sliding window를 통하여 해결하였다.
먼저 처음 인덱스 0에서부터 k개만큼의 스시를 선택한다.

해당하는 k개의 스시로 탐색한 다음, 제일 앞의 스시를 하나 제거하고 제일 뒤에 스시를 하나 추가하여 한번 더 탐색한다. 따라서, k 크기의 window를 오른쪽으로 하나씩 이동하며 탐색하여 초밥 가짓수의 최댓값을 구한다.

스시를 추가하고 제거할 때마다, 지금까지 기록된 스시 타입의 개수를 증감하며 현재 스시 타입의 개수를 구한다.

코드

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

public class Main {
	static int n, d, k, c, result;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk = new StringTokenizer(br.readLine());
    	n = stoi(stk.nextToken());
    	d = stoi(stk.nextToken());
    	k = stoi(stk.nextToken());
    	c = stoi(stk.nextToken());
    	
    	
    	int[] sushi = new int[n * 2];
    	for(int i = 0; i < n; i++)
    		sushi[i] = stoi(br.readLine());
    	
    	int[] type = new int[d + 1];
    	
    	for(int i = 0; i < k; i++)
    		sushi[n + i] = sushi[i];
    	
    	int cnt = 0;
    	// 스시 추가
    	for(int i = 0; i < k; i++) {
    		// 만약 처음 넣는 스시이면
    		if(type[sushi[i]] == 0) {
    			cnt++;
    		}
    		type[sushi[i]]++;	// 해당 스시의 개수 증가
    	}
    	
    	// 보너스 스시 추가
    	if(type[c] == 0) {
			cnt++;
		}
		type[c]++;
    	
		result = cnt;
    	
    	for(int i = k; i < n + k - 1; i++) {
    		// 앞 포인터의 스시 제거
    		type[sushi[i - k]]--;		
    		if(type[sushi[i - k]] == 0)		// 더 이상 해당 스시가 없으면
    			cnt--;
    		
    		// 뒤 포인터의 스시 추가
    		if(type[sushi[i]] == 0) {		// 새로 추가된 스시이면
    			cnt++;
    		}
    		type[sushi[i]]++;

    		result = Math.max(result, cnt);
    	}
    	
    	System.out.println(result);
    	br.close();
	}

	
	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

후기

알고리즘 분류의 두 포인터를 보고 아이디어를 얻어 푼 문제.

개선할 점

없습니다.