[BOJ] 20922 겹치는 건 싫어

문제

20922번: 겹치는 건 싫어

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

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

풀이

코드

#include <cstdio>
#include <algorithm>
using namespace std;
typedef pair<int, int> pii;

int n, k;
int arr[200000];
pii mx = {0, 0};
int cnt[100001];
int ans = 0;

void go() {
    int ri = 0;
    for(int i = 0; i < n; i++) {
        while (ri < n and mx.first <= k) {
            if (cnt[arr[ri]] + 1 > k) break;
            cnt[arr[ri]]++;
            if (mx.first < cnt[arr[ri]]) {
                mx = {cnt[arr[ri]], arr[ri]};
            }
            ri++;
        }
        if (mx.first <= k) ans = max(ans, ri - i);
        if (mx.second == arr[i]) mx.first--;
        cnt[arr[i]]--;
    }
    printf("%d", ans);
}

int main() {
    scanf("%d %d", &n, &k);
    for(int i = 0; i < n; i++) scanf("%d", &arr[i]);
    go();
}