[baekjoon 15961] 회전 초밥 (슬라이딩 윈도우, 두 포인터) (C++)

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

15961번: 회전 초밥

회전 초밥처럼 입력된 값을 돌면서 연속해서 먹을 수 있는 K개 중 서로 다른 종류의 초밥이 최대 몇 가지 있을 수 있는지 푸는 문제이다.

 

N이 최대 300만이므로 N^2은 당연히 시간 초과가 난다.

이렇게 K개의 수를 한번 훑어야 하는 경우 보통 슬라이딩 윈도우를 이용하면 O(N)만에 연산을 마칠 수 있다.

 

또한, 나는 가짓수를 관리해줄 때 map 자료구조를 사용해서 관리해주었다. 그리고 쿠폰을 통해 추가로 먹을 수 있는 음식이 map에 없다면 +1을 해주었다.

처음에 91%에서 틀렸었는데, 그냥 배열을 0부터 N까지만 보고 제출했다.

알고 보니 문제 이름이 회전 초밥인 것처럼 배열의 마지막까지만 보면 되는 것이 아니라 N-1, 0 1(인덱스)과 같이 원 모양으로 접근할 수 있는 문제였다.

따라서, 포인터의 인덱스를 % N으로 나눠줘야 한다.

 

0 1 2 3 4 5고 3개를 고르는 문제이면 012 123 234 345가 끝이 아니라 450 501까지 봐야 한다.

 

#include <iostream>
#include <unordered_map>
#include <algorithm>

using namespace std;

int N, D, K, C, arr[3000001];
int start, cnt, answer;
unordered_map<int, int> m;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> N >> D >> K >> C;
	for (int i = 0; i < N; i++) {
		cin >> arr[i];
	}


	for (int i = 0; i < K - 1; i++) { // k 4면 0 1 2 
		m[arr[i]]++;
	} // k -1개 넣어두고 시작

	int fin = K - 1;
	for(int i = 0 ; i < N ; i++){ // 회전초밥이므로 한 바퀴 돌자
		int del = arr[start];
		int cur = arr[fin%N];
		m[cur]++;
		int num = m.size();
		if (m.find(C) == m.end()) { // 쿠폰용 초밥이 없다면 +1
			answer = max(answer,num + 1);
		}
		else {
			answer = max(answer, num);
		}
		m[del]--;
		if (m[del] == 0) // 갯수가 0이라면 map에서 아예 지우자
			m.erase(m.find(del));
		start++;
		fin++;
	}
	cout << answer;
}