백준 s1 20922 겹치는 건 싫어 c++

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

20922번: 겹치는 건 싫어

 

문제

길이가 N인 수열이 주어질 때, 같은 원소가 K개 이하인 최장 연속 부분 수열의 길이 구하기

 

풀이

 

수도코드

while // en번째를 추가할 차례
	cnt[en번째 수]++
    if cnt[en번째 수] > K
    	while cnt[en번째 수] > K
        	st++ 하면서 범위 줄이기
    
   	length = en-st+1
    answer = max(length, answer)
    
    en++

 

전체 코드

/*boj s1 20922 겹치는 건 싫어*/
#include <iostream>
#define MAXN 200005
using namespace std;

int N, K;
int a[MAXN];
int cnt[100005];
int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> K;
    for (int i = 0; i < N; i++)
        cin >> a[i];

    int st = 0;
    int en = 0;
    int ans = 0;
    int len = 0;
    while (st < N && en < N) { // en번째를 추가할 차례
        cnt[a[en]]++;

        if (cnt[a[en]] > K) {
            while (cnt[a[en]] > K) {
                cnt[a[st]]--;
                st++;
            }
        }

        len = en - st + 1;
        ans = max(ans, len);

        en++;
    }

    cout << ans << "\n";
}