[백준 20922] - 곂치는 건 싫어 c++

 

문제

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

20922번: 겹치는 건 싫어

접근 방법

dp문제인 줄 알았다.

근데 투 포인터 문제라고 하길래 투 포인터가 뭔지 검색해봤다.

투 포인터를 알고 나서 다시 봤는데도 구현방법이 떠오르지 않아서, 다른 사람이 푼 걸 봤다.

그냥 끝까지 구현 해볼 걸 그랬다.

할 수 있었을 거 같은데, 아쉽다.

코드

#include <iostream>
#include <vector>

using namespace std;

int main() {

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

    vector<int> cnt(100001, 0);
    int start = 0;
    int max_num = 0;
    for (int i=0;i<n;i++) {
        cnt[arr[i]]++;
        if (cnt[arr[i]] > k) {
            while(cnt[arr[i]] > k) {
                cnt[arr[start]]--;
                start++;
                if (start >= n) break;
            }
        }
        max_num = max(max_num, i - start + 1);
    }

    cout << max_num << endl;
    

    return 0;
}

개선할 점

문제에서 제시한 정수 범위를 잘 못 적어 2번 에러 났다.

문제를 잘 보자.