[BOJ 15961] 회전 초밥

문제

BOJ 15961 회전초밥

유형

• 투 포인터

풀이

처음 생각한 풀이는 이거였다.

1. map에 처음부터 k개의 값을 넣는다.
2. n-1번 반복하며 arr[i] 값을 map에서 빼고 arr[i+k] 값은 map 넣는다.
3. c가 map에 들어있으면 map의 크기를 저장하고 없으면 map의 크기 + 1을 저장했다.

답은 맞게 나왔지만 시간초과가 발생하였다.
내가 생각했을 때는 절대 시간초과가 나지 않을 것 같은데 무슨 이유인지 모르겠다.

더 빠른 방법을 찾다가 굳이 map을 사용하지 않아도 배열을 사용하면 O(1)안에 모두 처리할 수 있다 (map을 사용해도 O(log(map.size())인데 왜 TLE인지는 모르겠지만)

visited라는 배열에 현재 k개 원소의 개수를 저장한다.
그리고 visited[c] = 1로 미리 저장해두어 k개 원소에 c가 포함되어 있는지 없는지 따로 확인하지 않도록 하였다.

코드

#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <cmath>
#include <fstream>

const int dx[4] = { 1,0,-1,0 };
const int dy[4] = { 0,-1,0,1 };

using namespace std;

int n, d, k, c;
vector<int> arr(3000001);
vector<int> visited(3000001);


int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false);
	cin >> n >> d >> k >> c;

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

	int cnt = 1;
	visited[c]++;
	for (int i = 0; i < k; i++) {
		visited[arr[i]]++;
		if (visited[arr[i]] == 1) cnt++;
	}

	int ans = cnt;

	for (int i = 0; i < n - 1; i++) {
		visited[arr[i]]--;
		if (visited[arr[i]] == 0) cnt--;
		visited[arr[(i + k) % n]]++;
		if (visited[arr[(i + k) % n]] == 1) cnt++;

		ans = max(ans, cnt);
	}

	cout << ans;

	return 0;
}