백준 20922번 겹치는 건 싫어

🔒[문제 url]

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

🪄전체 코드

#include <iostream>
#include <algorithm>
using namespace std;

int n,k;
int A[200001];//수열
int cnt[200001];//수열 내 각 원소의 갯수

void INPUT()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> k;
    for(int i = 0; i < n; i++) cin >> A[i];
}


void SOLVE()
{
    //Init(Two Pointer)
    int left = 0, right = 0;
    int ans = 1;
    cnt[A[left]]++;


    while(right < n)
    {
        if(cnt[A[right]] <= k)
        {//오른쪽 포인터가 가리키는 원소의 갯수가 k개 이하라면
            ans = max(ans,right-left+1);//최대 길이 갱신 후
            right++; cnt[A[right]]++;//오른쪽 포인터를 옮기고 원소 갯수 갱신

            if(cnt[A[right]] > k)
            {//포인터를 옮긴 후 원소의 갯수가 k를 초과한다면
                while(cnt[A[right]] > k && left <= right)
                {//왼쪽 포인터를 k개 이하가 될때까지 이동한다.
                 //이때 왼쪽 포인터는 오른쪽 포인터를 넘어가면 안 된다.
                    cnt[A[left]]--;
                    left++;
                }
                if(left == right)
                {//왼쪽 포인터의 이동이 끝난후, 오른쪽 포인터와 위치가 같다면 둘 다 옮긴다.
                    cnt[A[left]] = 0;
                    left++; right++;
                    cnt[A[left]] = 1;
                }
            }
        }
    }
    cout << ans;
}

int main()
{
    INPUT();
    SOLVE();
}

🥇문제 후기

GOLD5 미만 난이도는 알고리즘 및 풀이 설명을 주석으로 대체합니다.
주석을 참고해주세요.