[백준] 2531 회전초밥

✔️ 문제 링크

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

2531번: 회전 초밥

---

✔️ 문제 이해

◾ 회전하는 벨트위에 여러 종류의 초밥이 놓여있다. (종류는 번호로 표시)

◾ 임의의 한 위치부터 k개의 접시를 연속해서 먹으면 할인을 받을 수 있다.

◾ 한 장의 초밥 쿠폰이 주어진다. k개의 연속된 초밥 구간에 쿠폰에 해당하는 초밥이 없으면 해당 초밥을 준다.

◾ 할인은 받는 방식으로 초밥을 먹었을때, 최대 몇 개의 초밥을 먹을 수 있는지 구해야한다. 

---

✔️ 설계

◾ 회전 초밥 밸트에 대해 모든 k 길이의 구간을 확인하면 된다. 슬라이딩 윈도우를 사용한다.

◾ 회전 초밥 밸트이기에 초밥의 개수 + k 구간까지 확인한다. 

◾ 덱을 이용하여 슬라이딩 윈도우를 구현해서 문제를 풀었다. 

---

👨🏻‍💻 소스 코드

#include<iostream>
#include<map>
#include<algorithm>
#include<queue>
using namespace std;

int main() {
	int arr[30000];
	int n, d, k, c;

	cin >> n >> d >> k >> c;
	for (int i = 0; i < n; i++) { // 초밥 정보 입력
		cin >> arr[i];
	}

	deque<pair<int, int>> window; // 인덱스, 초밥 종류
	map<int, int> m; // 구간 : 초밥 종류, 개수
	int ret = -1;

	for (int i = 0; i < n+k; i++) {

		int idx = i;
		if (idx >= n) idx -= n;

		if (!window.empty() && window.front().first <= i - k ) {
			m[window.front().second]--; // 구간에서 초밥 뺴준다.
			if (m[window.front().second] <= 0)
				m.erase(window.front().second);
			window.pop_front(); // 윈도우에서 초밥을 빼준다.
		}

		window.push_back({ idx, arr[idx] });
		m[arr[idx]]++;

		if (window.size() == k) {
			int num = (int)m.size();
			if (m.count(c) == 0) num++;
			ret = max(ret, num);
		}
	}

	cout << ret;
	return 0;
	
}

---

✔️ 개선된 설계

◾ 위에서 덱을 이용해 슬라이딩 윈도우를 만들었다. 

◾ 하지만 아래 코드에서 확인할 수 있듯이, 굳이 덱으로 슬라이딩 윈도우를 만들 필요가 없다.

---

👨🏻‍💻 개선된 소스 코드

#include<iostream>
#include<algorithm>
using namespace std;

int table[30001];
int check[3001];

int main() {
	int n, d, k, c;

	cin >> n >> d >> k >> c;

	for (int i = 0; i < n; i++) {
		cin >> table[i];
	}

	int size = 0;
	int cnt = 0;

	for (int i = 0; i < k; i++) { // 첫 k 구간을 계산한다. 
		if (check[table[i]]++ == 0) // 처음 포함되는 초밥이라면, 카운트.
			cnt++;
	}

	int ret = cnt;

	for (int i = k; i < n + k; i++) { // n+k 전까지 k길이의 슬라이딩 윈도우를 민다. 

		//슬라이딩 윈도우를 미는 부분.
		if (--check[table[i - k]] == 0) cnt--; // 앞 초밥을 빼준다. check가 0이면, 종류 카운트 -1
		if (check[table[i%n]]++ == 0) cnt++; // 뒤 초밥을 더한다. check가 0이면, 종류 카운트 +1

		if (check[c] == 0) // 쿠폰을 고려하여 종류의 개수를 갱신한다. 
			ret = max(ret, cnt + 1);
		else
			ret = max(ret, cnt);
	}

	cout << ret;
	return 0;
}

---

✔️ 문제 회고

◾ 슬라이딩 윈도우 기법을 사용할 때 꼭 슬라이딩 윈도우를 만들지 않아도 되었다.

◾ 일정 크기의 윈도우에 대한 결과를 윈도우의 앞과 뒤에 대한 조작만으로 간단하게 구할 수 있었다.