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

🥈 Silver 1

✏️ 최종 솔루션

⭐️ Two Pointer
⭐️ left, right 옮겨주며 left, right 의 원소 개수 관리

1. left, right 는 0부터 시작
2. right 위치의 원소가 k 개 미만일 경우
   1) 수열 길이 갱신
   2) 현재 위치 원소 개수 갱신
   3) right 계속 늘려주기
   ➡️ right 의 원소 개수를 검사하는 시점이 현재 원소를 count 하기 이전이기 때문에 현재 시점에서 k 개 미만이어야 현재 원소까지 포함해서 k 개 이하가 될 수 있음
3. right 위치의 원소가 k 개일 경우
   1) left 위치의 원소 개수 줄이기
   2) left 늘려주기
   ➡️ 현재 위치 원소까지 포함하면 K 개를 초과하기 때문에 이때부터는 left 이동

📌 self feedback

원소 개수를 확인하는 시점이 현재 원소를 포함한 시점인지 포함하지 않은 시점인지 구분해서 계산하는 것이 중요했음

✏️ 최종 code

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

int main() {
    int n,k;
    cin >> n >>k;
    vector<int>v(n);
    for(int i=0;i<n;i++) {
        cin >> v[i];
    }

    int s=0,e=0,len=0;
    int visit[1000001]={0};
    while(e<n) {
       if(visit[v[e]]<k) {
           visit[v[e]]++;
           e++;
           len=max(len,e-s);
       }
        else if(visit[v[e]]==k){
            visit[v[s]]--;
            s++;
        }
    }

    cout << len;
}