15961번: 회전 초밥 - 슬라이딩 윈도우

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

15961번: 회전 초밥

 

관찰, 알고리즘

무식한 풀이로 해결하면, 연속해서 놓여있는 초밥 k개를 묶는 과정을 N번 반복하면 된다. 이때 시간복잡도는 O(kN)인데,  N의 범위는 3백만, k의 범위는 3천이므로 시간 초과가 날 것이다.

이전 단계에서 묶은 초밥에서 가장 뒤쪽 초밥은 빼고 다음에 오는 초밥을 포함시켜 묶으면, 좀 더 빠르게 초밥을 묶을 수 있을 것 같다. 즉, 이 문제는 슬라이딩 윈도우로 해결할 수 있다.

 

구현

묶은 초밥에서 각 초밥의 종류 당 개수가 몇 개 있는지 저장하는 배열 sushiCnt를 만든다.

초밥을 뺄 때 그 초밥의 개수가 0이 되면 전체 개수에서 1을 빼고, 초밥을 추가할 때 그 초밥의 개수가 이전에 0이었다면 전체 개수에서 1을 더한다. 이 과정을 N번 반복해 최댓값을 구한다.

초밥을 빼고 추가하는 과정의 시간복잡도는 O(1)이므로, 전체 시간복잡도는 O(N)이다.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tiii;

int N, d, k, c;
int sushi[3000000];
int sushiCnt[3001];
int cnt{0};
int ans;

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

	cin >> N >> d >> k >> c;
	for (int i{0}; i < N; i++)
		cin >> sushi[i];

	for (int i{0}; i < k; i++)
	{
		if (sushiCnt[sushi[i]]++ == 0)
			cnt++;
	}
	ans = cnt;

	for (int i{0}; i < N; i++)
	{
		int next = (i + k) % N;
		int pre = i;

		if (--sushiCnt[sushi[pre]] == 0)
			cnt--;
		if (sushiCnt[sushi[next]]++ == 0)
			cnt++;

		if (sushiCnt[c])
			ans = max(ans, cnt);
		else
			ans = max(ans, cnt + 1);
	}
	cout << ans << "\n";
}