백준 20922 겹치는 건 싫어 혼내주기

 

투 포인터로 구간에서 중복되는 숫자가 k개를 넘어가면 중복된 숫자가 구간에서 제외될 때 까지 왼쪽 포인터를 밀어주면 된다. 지금까지 한칸씩만 밀다가 조건을 만족할 때 까지 포인터를 움직이는 문제는 처음 만나서 좀 헤맸다. 

유연한 사고 능력이 부족하다!

 

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0)
using namespace std;

int arr[200000], cnt[100001];
int n, k;

void input() {
    fastio;
    cin >> n >> k;
    for(int i = 0; i < n; ++i) cin >> arr[i];
}

int main() {
    input();

    int ans = 0;
    for(int e = 0, s = 0; e < n; e++) {
        cnt[arr[e]]++;
        if(cnt[arr[e]] > k) {
            while(arr[s] != arr[e]) 
                cnt[arr[s++]]--;
            cnt[arr[e]]--;
            s++;
        }
        else 
            ans = max(ans, e+1-s);
    }
    cout << ans;
}