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

문제 링크

문제

홍대병에 걸린 도현이는 겹치는 것을 매우 싫어한다. 특히 수열에서 같은 원소가 여러 개 들어 있는 수열을 싫어한다. 도현이를 위해 같은 원소가 $K$개 이하로 들어 있는 최장 연속 부분 수열의 길이를 구하려고 한다.

 $100,000$ 이하의 양의 정수로 이루어진 길이가 $N$인 수열이 주어진다. 이 수열에서 같은 정수를 $K$개 이하로 포함한 최장 연속 부분 수열의 길이를 구하는 프로그램을 작성해보자.

입력

첫째 줄에 정수 $N$ ($1 \le N \le 200\,000$)과 $K$ ($1 \le K \le 100$)가 주어진다.

둘째 줄에는 ${a_1, a_2, ... a_n}$이 주어진다 ($1 \le a_i \le 100\,000$)

출력

조건을 만족하는 최장 연속 부분 수열의 길이를 출력한다.

예제 입력 / 출력

// 예제 입력 1
9 2
3 2 5 5 6 4 4 5 7

// 예제 출력 1
7

// 예제 입력 2
10 1
1 2 3 4 5 6 6 7 8 9

// 예제 출력 2
6

풀이

📍 알고리즘

• 위 문제는 투 포인터를 이용하는 문제이다.
• 투 포인터와 <unordered_map>을 사용하여 연속 숫자의 개수를 세주고 K개가 넘는 개수가 나왔을 때는 투 포인터의 시작 포인터 값을 이동하여 새로운 수열의 개수를 세면 된다.

#include <iostream>
#include <unordered_map>
#include <vector>

using namespace std;

int main(void) {

	int N, K, tmp, start, end, max = 1;
	unordered_map<int, int> m;
	vector<int> sequence;

	cin >> N >> K;

	for (int i = 0; i < N; i++) {
		cin >> tmp;
		sequence.push_back(tmp);
	}

	start = 0; end = 1;
	m[sequence[start]]++; 

	while (end != N) {
		
		m[sequence[end]]++;
		
		if (m[sequence[end]] > K) {
			if (max < end - start) max = end - start;
			while (m[sequence[end]] != K) {
				m[sequence[start]]--;
				start++;
			}
		}

		end++;
	}

	if (max < end - start) max = end - start;

	cout << max;


}