[백준] 2531번 : 회전 초밥 - 자바(JAVA)

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

2531번: 회전 초밥

 

문제 해석

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

초밥의 종류를 번호로 표현하며, 벨트 위에는 같은 종류의 초밥이 둘 이상 있을 수 있다.

 

초밥집에는 행사가 존재한다.

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

첫 번째 줄에는 N d k c 가 빈칸을 사이에 두고 주어진다.

 

두 번째 줄부터 N개의 줄에는 벨트의 한 위치부터 시작하여 회전 방향을 따라갈 때 초밥의 종류를 나타내는 정수가 주어진다.

 

제약조건

2 <= N <= 30,000

2 <= d <= 3,000

2 <= k <= 3,000 ( k <=N)

1 <= c <= d

 

출력

손님이 먹을 수 있는 초밥 가짓수의 최대값을 구하는 프로그램을 작성하라

 

문제 풀이 전 설계

N번만큼 접시에 담긴 초밥의 종류를 입력받는다

 

어떤 자료구조에 초밥의 종류를 저장한다.(탐색만 할 거니까 배열 생각)

배열은 인덱스 기준으로 탐색하니까 빠를것으로 예상 O(N)

이후에 0~N-1 번 인덱스에 대하여 k번씩 연속해서 탐색하며 초밥의 가짓수의 최댓값을 갱신한다.

이때 N-1번 인덱스의 경우에는 오른쪽으로 k번 탐색이 불가능하므로( 배열의 인덱스 초과)

나머지연산을 활용하여 인덱스가 N으로 넘어가는 경우에는 0으로 이동시킨다.

 

예를 들자면 이런 구조로 탐색을 합니다.

for(int i=0; i<N; i++){
	for(int j=0; j<K; j++){
		//배열의 범위를 초과할 수 있음!
		sushiKindInfo[i+j];
		// 나머지 연산을 활용
		sushiKindInfo[(i+j)%N];
    }
}

 

여기서 핵심은 중복을 하지 않는 것이 핵심이므로 Set 자료구조를 활용하여 Set에 저장한 뒤 Set의 크기를 비교한다면 좋을 것 같다.

 

주의할 점은 쿠폰이 존재하므로 쿠폰을 잘 활용해야 한다.

 

코드

package algorithm8;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;

public class RotatingSushi {
	static int countOfPlates, numberOfSushi, numberOfConsecutivePlates, couponNumber;
	static int maximumCountOfShsui;
	static int[] rotatingSushiBelt;
	static BufferedReader br;

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		inputSushiInfo();		
		searchMaximumCountOfShsui();
		printMaximumCountOfShsui();
	}

	private static void inputSushiInfo() throws IOException {
		br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		countOfPlates = Integer.parseInt(st.nextToken());
		numberOfSushi = Integer.parseInt(st.nextToken());
		numberOfConsecutivePlates = Integer.parseInt(st.nextToken());
		couponNumber = Integer.parseInt(st.nextToken());

		rotatingSushiBelt = new int[countOfPlates];

		for (int i = 0; i < countOfPlates; i++) {
			rotatingSushiBelt[i] = Integer.parseInt(br.readLine());
		}
	}

	private static void inputSushiInfoTest() {
		System.out.println(Arrays.toString(rotatingSushiBelt));
	}
	
	private static void searchMaximumCountOfShsui() {
		maximumCountOfShsui = 0;
		for(int i=0; i< countOfPlates; i++) {
			Set<Integer> set = new HashSet<Integer>();			
			for(int j=0; j< numberOfConsecutivePlates; j++) {
				set.add(rotatingSushiBelt[(i+j) % countOfPlates]);
			}
			set.add(couponNumber);			
			int temp = set.size();
			maximumCountOfShsui = maximumCountOfShsui > temp ? maximumCountOfShsui : temp;
		}
	}
	
	private static void printMaximumCountOfShsui() throws IOException {
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		bw.write(maximumCountOfShsui + "\n");
		bw.flush();
		bw.close();		
	}
}

중복을 처리하기 위해 Set 자료구조를 사용하였습니다.

반복문을 통해 연속된 값을 Set에 add 합니다.

마지막에는 set에 쿠폰의 값을 add 한 후 maximumCountOfShsui의 값을 계속 최대로 경신합니다.