[BOJ] 겹치는 건 싫어 20922번 C++

문제

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

 100000$100\,000$ 이하의 양의 정수로 이루어진 길이가 N인 수열이 주어진다.  이 수열에서 같은 정수를 K개 이하로 포함한 최장 연속 부분 수열의 길이를 구하는 프로그램을 작성해보자.

입력

첫째 줄에 정수 N (1 ≤ N ≤200000)과 K (1≤ K ≤ 100)가 주어진다.

둘째 줄에는 a1,a2,a3,...,an이 주어진다 (1≤ ai ≤100000)

 

출력

조건을 만족하는 최장 연속 부분 수열의 길이를 출력한다.

 

 

접근 방식

 

투 포인터를 사용해 숫자의 빈도수를 확인해야 한다.

먼저, 두개의 포인터를 시작 지점 1에 놓고

map을 활용해 빈도수를 확인한다.

만약 해당 숫자의 빈도수가 K가 넘는다면

이전에 기록한 빈도수 기록을 모두 초기화해주고 st 포인터를 옮긴다.

그렇지 않으면 en 포인터를 옆으로 이동시키면서 최장 연속 부분 수열의 최댓값을 구하면 된다~!

 

 

코드

 

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

int N,K,ans = 0;
int arr[200003];
map<int,int> mp;

int main() {
    cin>>N>>K;
    for(int i=1; i<=N; i++) cin>>arr[i];
    int st = 1;
    int en = 1;
    
    while (en <= N)
    {
        mp[arr[en]]++;

        while(mp[arr[en]] > K) { //앞에 원소들 빈도수 초기화
            mp[arr[st]]--;
            st++;
        }
        ans = max(ans, en-st+1);
        en++;
    }
    cout<<ans;
    
}