취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 2531번 문제인 회전 초밥이다.
문제는 아래 링크를 확인하자.

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

첫 접시부터 N번째 접시까지를 일렬로 나열한 뒤 바로 뒤에 이어서 첫 접시부터 N번째 접시까지를 다시 한번 나열한 길이 2N의 배열에서 연속한 k개의 접시를 확인하는 것으로 회전 초밥을 고를 모든 경우를 확인할 수 있음을 관찰하자.

현재 선택한 k개의 접시에 놓여있는 초밥 i의 개수를 cnt[i]라 하자. 이 때, 선택한 k개의 접시에 놓여있는 초밥의 가짓수는 cnt[i]가 양수인 i의 개수와 같게 된다.

이제 선택한 k개의 접시 중 첫번째 접시를 제외하고 마지막 접시의 다음 접시를 추가한다면 다른 k개의 접시를 고를 경우를 살펴볼 수 있게 된다. 이에 맞춰 기존의 초밥의 가짓수 및 사라지는 초밥의 종류와 새로 추가되는 초밥의 종류 및 cnt 배열을 활용하면 새 k개의 접시의 초밥의 종류를 빠르게 구해낼 수 있게 된다.

위와 같은 관찰을 이용해 문제를 해결하자. 글쓴이는 큐(queue) 자료구조를 이용해 이를 구현하였다.

아래는 제출한 소스코드이다.

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

int N, D, K, C;
int arr[60000];
int cnt[3001];
queue<int> que;
int types;
int mx;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> D >> K >> C;
	for (int i = 0; i < N; i++) {
		int x; cin >> x;
		arr[i] = arr[i + N] = x;
	}

	N *= 2;

	for (int i = 0; i < K; i++) {
		int& cur = arr[i];
		if (!cnt[cur]) types++;
		cnt[cur]++;
		que.push(arr[i]);
	}

	mx = max(mx, cnt[C] ? types : types + 1);
	for (int i = K; i < N; i++) {
		cnt[que.front()]--;
		if (!cnt[que.front()]) types--;
		que.pop();
		int& cur = arr[i];
		if (!cnt[cur]) types++;
		cnt[cur]++;
		que.push(arr[i]);

		mx = max(mx, cnt[C] ? types : types + 1);
	}

	cout << mx;
}