[BaekJoon] 2531 회전 초밥

1.  문제 링크

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

2.  문제

요약

• 회전하는 벨트 위에 여러 가지 종류의 초밥이 접시에 담겨 놓여 있고, 손님은 이 중에서 자기가 좋아하는 초밥을 골라서 먹습니다.
• 초밥의 종류는 번호로 표현됩니다.
• 새로 문을 연 회전 초밥 음식점이 다음과 같은 두 가지 행사를 통해서 매상을 올리고자 합니다.
  1. 벨트의 임의의 한 위치부터 k개의 접시를 연속해서 먹을 경우 할인된 정액 가격으로 제공합니다.
  2. 각 고객에게 초밥의 종류 하나가 쓰인 쿠폰을 발행하고, 1번 행사에 참가할 경우 이 쿠폰에 적혀진 종류의 초밥 하나를 추가로 무료로 제공합니다. 만약 이 번호에 적혀진 초밥이 현재 벨트 위에 없을 경우, 새로 만들어 손님에게 제공합니다.
• 회전 초밥 음식점의 벨트 상태, 메뉴에 있는 초밥의 가짓수, 연속해서 먹는 접시의 개수, 쿠폰 번호가 주어졌을 때, 손님이 먹을 수 있는 초밥 가짓수의 최댓값을 구하는 문제입니다.
• 입력: 첫 번째 줄에 2보다 크거나 같고 30,000보다 작거나 같은 접시의 수 N, 2보다 크거나 같고 3,000보다 작거나 같은 초밥의 가짓수 d, 2보다 크거나 같고 3,000 또는 N보다 작거나 같은 연속해서 먹는 접시의 수 k, 1보다 크거나 같고 d보다 작거나 같은 쿠폰 번호 c가 주어지고 두 번째 줄부터 N개의 줄에는 벨트의 한 위치부터 시작하여 회전 방향을 따라갈 때 초밥의 종류를 나타내는 1 이상 d 이하의 정수가 각 줄마다 주어집니다.
• 출력: 첫 번째 줄에 주어진 회전 초밥 벨트에서 먹을 수 있는 초밥의 가짓수의 최댓값을 하나의 정수로 출력합니다.

3.  소스코드

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

public class Main {
	public int getMaxTypeNum(int[] sushi_nums, int d, int k, int c) {
		int max = 0;
		int[] sushies = new int[d + 1];
		for(int i = 0; i < k; i++) {
			if(sushies[sushi_nums[i]] == 0) {
				max++;
			}
			sushies[sushi_nums[i]]++;
		}
		int count = max;
		for(int i = 1; i < sushi_nums.length; i++) {
			if(max <= count) {
				if(sushies[c] == 0) {
					max = count + 1;
				} else {
					max = count;
				}
			}
			int end = (i + k - 1) % sushi_nums.length;
			if(sushies[sushi_nums[end]] == 0) {
				count++;
			}
			sushies[sushi_nums[end]]++;
			sushies[sushi_nums[i - 1]]--;
			if(sushies[sushi_nums[i - 1]] == 0) {
				count--;
			}
		}
		return max;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		String[] input = br.readLine().split(" ");
		int n = Integer.parseInt(input[0]);
		int d = Integer.parseInt(input[1]);
		int k = Integer.parseInt(input[2]);
		int c = Integer.parseInt(input[3]);
		int[] sushi_nums = new int[n];
		for(int i = 0; i < sushi_nums.length; i++) {
			sushi_nums[i] = Integer.parseInt(br.readLine());
		}
		br.close();
		Main m = new Main();
		bw.write(m.getMaxTypeNum(sushi_nums, d, k, c) + "\n");
		bw.flush();
		bw.close();
	}
}

4.  접근

• 이 문제는 투포인터를 이용하여 구할 수 있는 문제입니다.
• 우선 주어진 초밥 번호에서 첫 번째 번호의 초밥부터 k개의 초밥을 먹는 경우를 구합니다.
• 각 초밥 번호가 k개를 선택했을 때 몇 개가 포함되어있는지를 나타내는 배열 sushies를 생성합니다.
• 첫 번째 초밥 번호부터 k개를 확인하여 만약 아직 해당 초밥 번호가 선택한 k개에 한 개도 들어있지 않다면 초밥의 가짓수의 최댓값을 나타내는 변수 max 값을 1 올리고 해당 초밥 번호가 포함되었기 때문에 해당 초밥 번호의 sushies 값을 1 증가시킵니다. 우선 초기 max값을 첫 번째 초밥 번호가 시작 초밥일 경우에서의 초밥의 가짓수로 초기화합니다.
• 이후에 두 번째 초밥부터 마지막 초밥까지 각각을 시작 초밥으로 두었을 때의 초밥의 가짓수를 구하고 그 중 최댓값을 구합니다.
• 반복문의 각 실행에서의 초밥의 가짓수를 count라는 변수에 담습니다.
• 만약 max값이 count값보다 작거나 같다면 더 많은 가짓수가 존재할 수 있다는 뜻이므로 이 때는 쿠폰 번호 초밥이 k개 고른 초밥 내에 포함되어 있는지 확인하고 그렇다면 max값을 (count + 1)로 변경하고 그렇지 않다면 count값으로 변경합니다.
• 반복문 각 실행에서의 초밥의 가짓수를 구하는 방법은 이전 실행에서의 sushies 값들과 count 값을 이용합니다.
• 각 반복문에서 시작 초밥이 하나씩 뒤로 밀리기 때문에 바로 이전 실행에서의 시작 초밥은 현재 실행에서 k개에 포함되지 않게 됩니다. 그렇기 때문에 이전 실행에서의 시작 초밥 번호에 해당하는 sushies 값을 1 줄이고 만약 줄인 후에 sushies 값이 0이 됐다면 고른 k개에 포함되지 않는다는 뜻이기 때문에 1을 줄입니다.
• 각 반복문에서 k개의 초밥을 고를 때 마지막 번호의 index는 (시작 초밥 번호의 index + k - 1)을 N으로 나눈 나머지 값이 되게 됩니다.
• 마지막 번호는 이번 실행에서 추가되는 번호이기 때문에 해당 번호의 sushies 값이 0이라면 가짓수가 추가되는 것이기 때문에 count를 1 증가시키고 해당 번호의 sushies 값을 1 증가시킵니다.
• 각 반복문마다 최댓값이 갱신되기 때문에 반복문이 종료된 후의 max값이 주어진 회전 초밥 벨트에서 먹을 수 있는 초밥의 가짓수의 최댓값이 됩니다.