회전 초밥 먹고 싶다
👀 문제
15961번: 회전 초밥 ✨ 골드 4
회전 초밥 음식점에는 회전하는 벨트 위에 여러 가지 종류의 초밥이 접시에 담겨 놓여 있고, 손님은 이 중에서 자기가 좋아하는 초밥을 골라서 먹는다. 초밥의 종류를 번호로 표현할 때, 다음 그림은 회전 초밥 음식점의 벨트 상태의 예를 보여주고 있다. 벨트 위에는 같은 종류의 초밥이 둘 이상 있을 수 있다.
새로 문을 연 회전 초밥 음식점이 불경기로 영업이 어려워서, 다음과 같이 두 가지 행사를 통해서 매상을 올리고자 한다.
-
원래 회전 초밥은 손님이 마음대로 초밥을 고르고, 먹은 초밥만큼 식대를 계산하지만, 벨트의 임의의 한 위치부터 k개의 접시를 연속해서 먹을 경우 할인된 정액 가격으로 제공한다.
-
각 고객에게 초밥의 종류 하나가 쓰인 쿠폰을 발행하고, 1번 행사에 참가할 경우 이 쿠폰에 적혀진 종류의 초밥 하나를 추가로 무료로 제공한다. 만약 이 번호에 적혀진 초밥이 현재 벨트 위에 없을 경우, 요리사가 새로 만들어 손님에게 제공한다.
위 할인 행사에 참여하여 가능한 한 다양한 종류의 초밥을 먹으려고 한다. 위 그림의 예를 가지고 생각해보자. k=4이고, 30번 초밥을 쿠폰으로 받았다고 가정하자. 쿠폰을 고려하지 않으면 4가지 다른 초밥을 먹을 수 있는 경우는 (9, 7, 30, 2), (30, 2, 7, 9), (2, 7, 9, 25) 세 가지 경우가 있는데, 30번 초밥을 추가로 쿠폰으로 먹을 수 있으므로 (2, 7, 9, 25)를 고르면 5가지 종류의 초밥을 먹을 수 있다.
회전 초밥 음식점의 벨트 상태, 메뉴에 있는 초밥의 가짓수, 연속해서 먹는 접시의 개수, 쿠폰 번호가 주어졌을 때, 손님이 먹을 수 있는 초밥 가짓수의 최댓값을 구하는 프로그램을 작성하시오.
예제 입력
8 30 4 30
7
9
7
30
2
7
9
25예제 출력
5🔑 키포인트
ArrayDeque
✍️ 코드
📍 뒤로 추가해 주고 앞에서부터 빼기 위해 ArrayDeque를 사용하여 풀었다
1️⃣ 먼저 초기값으로 k개를 deque에 넣어 주고, 초밥 번호를 인덱스로 삼아 count배열에 +1 해 준다. answer의 초기값은 만약 해당 구간에 쿠폰 번호와 같은 초밥이 없다면 kind + 1, 아니면 kind
2️⃣ 회전 초밥이므로 맨 마지막 초밥이 시작점이 될 때까지 반복해야 한다. pollFirst 와 offerLast 를 사용해 반복하며 구간별 초밥 종류를 세 준다.
3️⃣ 그중 가장 많은 초밥 가짓수가 정답!
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.StringTokenizer;
public class BOJ15961_회전초밥 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken()); // 접시의 수
int d = Integer.parseInt(st.nextToken()); // 가짓 수
int k = Integer.parseInt(st.nextToken()); // 연속해서 먹는 가짓수
int c = Integer.parseInt(st.nextToken()); // 쿠폰 번호
int[] nums = new int[n];
for (int i = 0; i < n; i++) {
nums[i] = Integer.parseInt(br.readLine());
}
int[] count = new int[d + 1]; // 초밥 종류별 카운트
ArrayDeque<Integer> dq = new ArrayDeque<>();
int kind = 0;
// 초깃값
for (int i = 0; i < k; i++) {
int s = nums[i];
dq.offerLast(s);
if (count[s] == 0) {
kind++;
}
count[s]++;
}
int answer = kind + (count[c] == 0 ? 1 : 0);
// 슬라이딩 윈도우
for (int i = 1; i < n; i++) {
int remove = dq.pollFirst();
count[remove]--;
if (count[remove] == 0) {
kind--;
}
int next = nums[(i + k - 1) % n];
dq.offerLast(next);
if (count[next] == 0) {
kind++;
}
count[next]++;
int total = kind + (count[c] == 0 ? 1 : 0);
answer = Math.max(answer, total);
}
System.out.println(answer);
}
}
