백준 20922번 겹치는 건 싫어

문제 요약

길이 $N$인 수열 $a$와 $K$가 주어진다. 연속 부분수열 중에서 같은 정수가 $K$개 이하로 포함되는 최장 연속 부분 수열의 길이를 출력하시오.

N은 최대 20만, K는 최대 100, 주어지는 수들의 범위는 1부터 10만까지이다.

풀이

연속 부분 수열이기 때문에 투포인터를 사용할 수 있다. 현재 보고 있는 수열의 범위를 $[s,e)$라고 하자.

만약 e번째 수의 등장횟수가 이미 K번이라면 s를 오른쪽으로 옮기면서 현재 보고 있는 부분 수열의 길이를 줄여나간다.

그러다가 e번째 수의 등장횟수가 K보자 작아졌다면 s를 오른쪽으로 옮기는 것을 그만두고 다시 e를 늘련간다.

이렇게 하면 답을 찾을 수 있다.

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

int N, K;
int cnt[100005];
int a[200005];
int main() {
    cin.tie(nullptr); ios::sync_with_stdio(false);
    cin >> N >> K;
    for(int i=1;i<=N;++i) cin >> a[i];
    int s = 1, e = 1;
    int ans = 0;
    while(e <= N && s <= e) {
        while(e <= N && cnt[a[e]] <= K) {
            if(cnt[a[e]] == K) 
                break;
            cnt[a[e]]++;
            ans = max(ans, e-s+1);
            ++e;
        }
        while(s < e) {
            if(cnt[a[s]] == K) {
                --cnt[a[s++]];
                break;
            }
            --cnt[a[s++]];
        }
    }
    cout << ans << '\n';
    return 0;
}