백준 BOJ 2531+15961 - 회전 초밥

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

2531번: 회전 초밥

연속된 고정 길이의 회전초밥들을 골랐을때

+ 고정된 한개의 메뉴가 있을때,

초밥의 종류를 최대한 다양하게 가져가도록 하는 문제

 

15961번은 범위가 매우 크기 때문에 브루트포싱으로 해결할 수 없고,

회전초밥의 길이가 고정적이라는 점에서 착안해서

슬라이딩 윈도우 알고리즘을 적용해서 문제를 해결했다.

 

초밥의 종류를 관리하는데에는 다양한 방법이 있을 수 있는데,

일반적인 배열의 인덱스를 사용해서 관리할 수도 있겠지만

이러면 초밥의 종류를 셀 변수를 하나 더 선언해주거나

추가적인 시간이 필요하게 된다.

 

그래서 나는 unordered_map 에

index로 초밥의 종류,

value로 해당 초밥의 수

를 저장했고,

 

value 가 0이 되면 unordered_map::erase 를 이용해서

삭제 해준 뒤

전체 초밥의 종류는 unordered_map::size 를 이용해 구했다.

N범위가 커서 시간제한이 빡빡한 편인지

그냥 map으로 구현시 TLE를 받게 된다.

참고해야할듯.

 

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

int N,D,K,C;
int sushi[3456789] = {0};
int ans = -1;

unordered_map<int,int> curr;

int idx(int k){
	return (k+N)%N;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	cin >> N >> D >> K >> C;
	for(int i=0; i<N; i++){
		cin >> sushi[i];
	}
	
	for(int i=0; i<K; i++){ curr[sushi[i]]++; }
	ans = max(ans, (int)curr.size());
	curr[C]++;
	
	for(int i=K; i<N+K; i++){
		curr[sushi[idx(i)]]++;
		curr[sushi[idx(i-K)]]--;
		if(curr[sushi[idx(i-K)]] == 0){
			curr.erase(sushi[idx(i-K)]);
		}
		ans = max(ans, (int)curr.size());
	}
	cout << ans;
	return 0;
}