[BOJ] - 회전 초밥 / 15961 (Java)

[BOJ] - 회전 초밥 / 15961 (Java)

[BOJ] - 회전 초밥 / 15961 (Java)

1. 문제 접근

주어진 회전 초밥 벨트에서 먹을 수 있는 초밥의 가짓수의 최댓값을 구하면 된다.

 

입력값을 살펴보면 2 ≤ N ≤ 3,000,000, 2 ≤ d ≤ 3,000, 2 ≤ k ≤ 3,000 (k ≤ N), 1 ≤ c ≤ d이다.

 

초밥 벨트 위에 놓여질 수 있는 초밥의 최대값은 300만, 선택할 수 있는 초밥 개수의 최대값은 3000으로 모든 구간에 대해 초밥의 가지 수를 계산하게 되면 대략 90억 번의 연산이 발생할 수 있다.

 

따라서 한 번의 순회만에 초밥 가지 수의 최대값을 구해야 한다.

 

한 번의 순회만에 구하기 위해 슬라이딩 윈도우와 `Map`을 사용해서 풀었다.

 

`front`, `rear`를 사용해 한 칸씩 윈도우를 움직이며 `front`의 초밥은 빼고, `rear`의 초밥은 더하는 방식으로 구현했다.

 

front = 0;
rear = (front + k) % N;

 

또한, 현재 선택한 초밥의 정보를 저장하기 위한 자료구조로는 `HashMap<Integer, Integer>`를 사용했다.

 

`key`값은 초밥의 번호, `value`는 해당 초밥의 개수다.

 

private static Map<Integer, Integer> currSushiState;

 

 초밥을 더하고 빼는 로직은 아래와 같다.

 

• 더하는 로직
  • 현재 초밥의 상태(`currSushiState`)에 더하고자 하는 초밥이 있을 경우
    • 해당 초밥의 개수를 하나 증가시킨다
  • 현재 초밥의 상태(`currSushiState`)에 더하고자 하는 초밥이 없을 경우
    • 해당 초밥에 해당하는 `key`값을 추가하고 `value`를 1로 초기화 한다.

if (currSushiState.containsKey(insertSushi)) {
    currSushiState.put(insertSushi, currSushiState.get(insertSushi) + 1);
} else {
    currSushiState.put(insertSushi, 1);
}

• 빼는 로직
  • 현재 초밥의 상태(`currSushiState`)에 빼고자 하는 초밥의 개수가 1개일 경우
    • 해당 초밥의 `key`값을 삭제시킨다.
  • 현재 초밥의 상태(`currSushiState`)에 빼고자 하는 초밥의 개수가 1개 이상일 경우
    • 해당 초밥의 개수를 하나 감소시킨다.

if (currSushiState.get(removeSushi) == 1) {
    currSushiState.remove(removeSushi);
} else {
    currSushiState.put(removeSushi, currSushiState.get(removeSushi) - 1);
}

 

마지막으로 보너스 초밥을 확인하고 현재 초밥에 포함되어있지 않으면 먹을 수 있는 초밥 가지 수를 하나 증가시키고, `front`, `rear`값을 갱신한다.

 

if(!currSushiState.containsKey(c)) {
    ++localCnt;
}

 

for (; front < N; ++front) {
	...
    // rear 갱신
    rear = (rear + 1) % N;
}

---

2. 코드

package boj;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;

/**
 * [BOJ] - 회전 초밥 / 15961 
 * @author JinHxxxxKim
 * 
 * 1. 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c를 입력받는다.
 * 2. 접시의 상태를 입력받는다.
 * 3. front = 0 ~ N-1 까지, rear = k ~ (N-1+k)%k까지 슬라이딩 윈도우를 적용한다.
 * 		- front는 포함, rear는 미포함
 * 4. 각 접시를 확인한 뒤, Map에 넣는다. <초밥의 종류, 현재  초밥의 개수>
 * 		- 보너스 접시를 포함 했을 때의 총 가짓 수(Key의 수)를 counting하고 max값을 업데이트 한다.
 */
public class Sol_15961 {
	private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	private static StringBuilder sb = new StringBuilder();
	private static StringTokenizer st;

	// 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c
	private static int N, d, k, c;
	private static Map<Integer, Integer> currSushiState;
	private static int maxCnt;
	private static int[] sushiArray;
	
	// 슬라이딩 윈도우
	private static int front, rear;
	
	public static void main(String[] args) throws Exception {
		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());
		
		maxCnt = 0;
		
		sushiArray = new int[N];
		for (int idx = 0; idx < N; ++idx) {
			sushiArray[idx] = Integer.parseInt(br.readLine().trim());
		}
		
		// 슬라이딩 윈도우 시작
		front = 0;
		rear = (front + k) % N;
		currSushiState = new HashMap<>();
		for (int idx = front; idx < rear; ++idx) {
			int currSushi = sushiArray[idx];
			// 해당 접시가 이미 있다면, 개수 하나 증가
			if(currSushiState.containsKey(currSushi)) {
				currSushiState.put(currSushi, currSushiState.get(currSushi)+1);
			}
			// 없다면
			else {
				currSushiState.put(currSushi, 1);
			}
		}
		
		int localCnt = currSushiState.size();
		if(!currSushiState.containsKey(c)) {
			++localCnt;
		}
		maxCnt = localCnt;
		
		// front를 빼고, rear를 넣는다.
		for (; front < N; ++front) {
			// front 빼기
			int removeSushi = sushiArray[front];
			if (currSushiState.get(removeSushi) == 1) {
				currSushiState.remove(removeSushi);
			} else {
				currSushiState.put(removeSushi, currSushiState.get(removeSushi) - 1);
			}
			
			// rear 넣기
			int insertSushi = sushiArray[rear];
			
			// 해당 접시가 이미 있다면, 개수 하나 증가
			if (currSushiState.containsKey(insertSushi)) {
				currSushiState.put(insertSushi, currSushiState.get(insertSushi) + 1);
			}
			// 없다면
			else {
				currSushiState.put(insertSushi, 1);
			}
			
			// rear 갱신
			rear = (rear + 1) % N;
			// 최대 초밥 가지 수 갱신
			localCnt = currSushiState.size();
			if(!currSushiState.containsKey(c)) {
				++localCnt;
			}
			maxCnt = Math.max(localCnt, maxCnt);
		}
		
		System.out.println(maxCnt);
	}
}

---

3. 디버깅

처음 발상할 당시, `Map`이 아닌 `Set`을 사용하여 구현하고자 하였지만, 현재 먹을 수 있는 초밥의 개수를 저장할 수 없다는 것을 파악하고 `Map` 자료구조로 변경하였다.

 

또한, `Map`을 사용하지 않고, 배열을 사용해 풀게 되면 실행 시간을 1/2정도까지 줄일 수 있다.

---

4. 결과