[BOJ/20922] 겹치는 건 싫어, c++

www.acmicpc.net/problem/20922

20922번: 겹치는 건 싫어

한줄 후기 : 덱이 진짜 편한거 같어

 

신촌 겨울 알고리즘 캠프 초급 모의고사 문제다.

저번에 한번 심심해서 풀어봤다.

문제 이해는 참 쉬웠는데 은근 뭐로 접근해야할 지 고민한 문제.

그러다 덱을 써보자 하고 덱을 써서 풀었다.

길이가 20만이라 당연히 완전탐색은 무리다.

//AC
//BOJ 20922 겹치는 건 싫어

#include <iostream>
#include <deque>
using namespace std;
deque<int> dq;
int count[101010];
int main(){
	int N, K, a, cnt=0, ans=0;
	scanf("%d %d", &N, &K);
	for(int i=0; i<N; i++){
		scanf("%d", &a);
		count[a]++;
		if(dq.empty()){
			dq.push_back(a);
		}
		else{
			if(count[a] <= K){
				dq.push_back(a);
			}
			else{
				int tmp = -1;
				while(tmp != a && !dq.empty()){
					tmp = dq.front();
					dq.pop_front();
					count[tmp] -= 1;
				}
				dq.push_back(a);
			}
		}
		cnt = dq.size();
  		ans = max(ans,cnt);
	}
	printf("%d", ans);
	return 0;
}

숫자를 받으면서 덱에 넣어주기 전에 지금까지 나온 해당 수의 개수를 카운팅 해준다.

count[a]++ 이 부분

이제 덱에 넣어야 하는데

만약에 현재 a의 개수가 허용 가능한 K 보다 작으면 바로 덱에 넣고, 아닐 경우 덱에 앞쪽에서부터 해당 수가 나올 때 까지 숫자를 다 뺀다.

해당 수가 나오면 덱에 넣어준다.

그러면 덱에 있는 숫자들은 모두 지금까지 나온 수들로 만들 수 있는 범위 내에 허용되는 최장 길이 수열이 된다.

매번 덱의 사이즈를 현재 최댓값이랑 비교하여 마지막 ans를 출력하면 된다.

 

풀고나서 알고리즘 분류를 보니 투포인터네? 덱으로도 풀린다 ㅎㅎ