백준 2531번 회전 초밥 C++

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

연속으로 k개의 초밥을 먹고 쿠폰에 쓰여있는 초밥까지 먹었을 때 최대 몇 가지의 초밥을 먹을 수 있는지를 구하는 문제이다.

 

우선 마지막 초밥에서 처음 초밥으로 이어지기 때문에 초밥의 정보를 저장하는 배열에 처음부터 k-1개만큼 더한 배열을 만들었다

예제의 입력을 예로 들면 7 9 7 30 2 7 9 25 의 배열에 k-1 즉 3개를 처음부터 더한 배열

7 9 7 30 2 7 9 25 7 9 7 을 만들었다. 이렇게 하면 마지막 원소 25부터 4개를 먹었을 때 25 7 9 7로, 마지막에서 처음으로 돌아가는 것과 같다.

 

그리고 unordered_map을 <int(초밥의 종류), int(초밥의 개수)> 로 만들고 k개만큼을 슬라이딩 윈도우 방식으로 탐색하면서 새로운 초밥이 들어오면 초밥을 추가하고, 원래 있던 초밥이 또 들어오면 해당 초밥의 개수를 증가시키고, 초밥이 나가면 해당 초밥의 개수를 줄여주고, 만약 초밥의 개수가 0이 되면 erase를 통해 초밥의 종류의 수를 맞춰주었다.

그리고 쿠폰에 있는 초밥은 매 경우마다 추가해주고 빼주고를 반복하면서 문제를 해결하였다.

 

문제를 해결하기 위해 unordered_map에 대한 정보를 찾다가 m[0]++ 이런 식으로 정보를 추가할 수 있다는 것을 알게 되었다. 이 문제를 해결할 때 매우 편리한 기능이었다. 좋은 정보를 얻은 것 같다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <unordered_map>
#include <unordered_set>

using namespace std;
typedef long long ll;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n, d, k, c;
	int num;
	cin >> n >> d >> k >> c;
	vector<int> v(n + k - 1);
	for (int i = 0; i < n; i++) {
		cin >> v[i];
	}
	for (int i = 0; i < k - 1; i++) {
		v[i + n] = v[i];
	}
	unordered_map<int, int> m;
	int ans = 0;
	for (int i = 0; i < k; i++) {
		m[v[i]]++;
	}
	m[c]++;
	ans = m.size();
	m[c]--;
	if (m[c] == 0) m.erase(c);
	
	for (int i = 0; i < n - 1; i++) {
		m[v[i]]--;
		if (m[v[i]] <= 0) m.erase(v[i]);
		m[v[i + k]]++;
		m[c]++;
		ans = max(ans, (int)m.size());
		m[c]--;
		if (m[c] <= 0) m.erase(c);
	}
	cout << ans;
};