문제 출처

1. 문제설명

  • 양의 정수 수열 N이 주어진다.
    • 1<=$a_n$<=100,000
    • 1<=N<=200,000
  • 이 수열에서 같은 정수를 K개 이하로 포함한 최장 연속 부분 수열의 길이를 구하라



2. 알고리즘 설계

  • 수열의 첫 번째 부분부터 탐색하면서 정수 개수 카운팅
  • 만약, K개를 넘어서면
    • 수열의 start 위치의 값을 1개 감소
    • start를 다음 칸으로 이동
  • end 계속해서 증가
    • end는 현재 탐색중인 위치
  • 예제
    • LIS와 달리 값의 정렬은 중요하지 않음.
    • 카운팅이 K를 초과하지만 않으면 됨.
    9 2
3 2 5 5 6 4 4 5 7

// out:7
// 3, 2, 5, 5, 6, 4, 4



3. 로직

  • unordered_map 사용
    • <int, int>형
    • key: 수열, value: 개수
  • map[key].value가 k개를 넘지 않을 때까지
    • 카운팅
  • K 값을 넘어서도 해에 도달했을 수 있으므로,
    • K값을 넘어섰을 때, 탐색이 끝났을 때 모두 검사


4. 전체 코드

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	
	int n, k;
	cin >> n >> k;

	vector<int> v(n);
	for (int i = 0; i < n; i++)
		cin >> v[i];

	unordered_map<int, int> m;
	int start = 0, end = 1, ans = 1;
	
	m[v[start]]++;
	while (end < n) {
		m[v[end]]++;
		if (m[v[end]] > k) {
			if (ans < end - start) ans = end - start;
			while (m[v[end]] > k)
				m[v[start++]]--;
		}
		end++;
	}
	if (ans < end - start) ans = end - start;
	cout << ans;
}


5. 소감

  • map vs unordered_map
    • 키, 값을 저장할 수 있는 컨테이너
    • map은 red-black tree 기반으로 키의 순서 유지
    • unordered_map은 해시 테이블을 사용해 키의 순서 유지X