[백준 C++] 20922 겹치는 건 싫어

 

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

20922번: 겹치는 건 싫어

 

 

투포인터 글쓸때 한번 시도해봤다가 코드가 꼬여서 덮어뒀던 문제이다...

문제에서 요구하는 것이 "최장 연속 부분 수열의 길이"이므로 투포인터 알고리즘으로 해결 가능할 것이다.

투포인터 알고리즘의 개념은 아래 링크에 있다.

https://chhggg.tistory.com/15

투포인터 알고리즘 (Two pointers Algorithm)

 

---

 

 

우선 내 계획은 다음과 같다.

1. cnt[100,000]배열을 선언한다. 해당 배열을 이용해 부분 수열에 중복된 원소가 K개를 넘었는 지를 확인할 것이다.

2. 우선 end포인터를 ++한다. 그러고 해당 idx에 해당하는 원소를 cnt배열에 반영 (end =1이고 a[1]=8이면 cnt[8]++)

3. 만약 ++한 결과가 K보다 크다면 cnt가 K이하가 될 때까지 srt++를 수행하고 최장 연속 부분 수열의 길이(res)를 업데이트할지말지 판단. K보다 작다면 end++

그 후 end가 N이 될때까지 2, 3번을 반복한다!

 

아래는 의식의 흐름대로 짠 코드이다. 뭔가 되게 난잡해보인다. 필요없어보이는 while문도 있다. 

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
ll n, k, a[200'010];
ll st, ed, cnt[100'010], res;



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

	for (ll i = 0; i < n; i++) cin >> a[i];

	cnt[a[ed]]++;
	ed++;
	cnt[a[ed]]++;

	while (ed <= n) {
		ll tmp = ed - st;
		res = max(res, tmp);

		if (cnt[a[ed]] > k) {
			while (cnt[a[ed]] > k) {
				cnt[a[st]]--;
				st++;
			}
		}
		else {
			ed++;
			cnt[a[ed]]++;
		}
	}
	
	cout << res;
	
}

 

좀 더 깔끔하게 고친 코드. 제대로 동작하는지 확인하기 위한 pr_cnt 함수를 이용했다.

위 코드는 증가시킨 것이 k보다 클 때 st를 움직였다면, 이 코드는 증가시키기 전 cnt값이 k이하이면 st를 조정하는 방식이다.

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
ll n, k, a[200'010];
ll st, ed, cnt[100'010], res;

void pr_cnt() {
	for (ll i = 0; i < 9; i++) {
		cout << cnt[i] <<' ';
	}
	cout << '\n';
}


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

	for (ll i = 0; i < n; i++) cin >> a[i];

	while (ed < n) {
		pr_cnt();
		if (cnt[a[ed]] >= k) {
			cnt[a[st]]--;
			st++;
		}
		else {
			cnt[a[ed]]++;
			ed++;
		}

		ll tmp = ed - st;
		res = max(res, tmp);
	}

	cout << res;

}