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

시간 복잡도

• N이 최대 200,000 이기 때문에 $O(N^2)$의 시간복잡도를 가지는 알고리즘은 사용할 수 없습니다.

문제 접근법

• 포인터를 하나씩 움직이며 같은 수가 K개 나왔다면 길이를 저장하고 포인터를 옮깁니다.
• 해당 길이의 최댓값을 구합니다.

코드

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <string>
#include <climits>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>

using namespace std;

using int32 = long;
using int64 = long long;

static vector<int> v;
static int arr[100001] = {};

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int N, K;
    cin >> N >> K;

    v.resize(N);

    for (int i = 0; i < N; i++)
        cin >> v[i];

    int l = 0, r=0;
    int result = 0;
    while(r<v.size())
    {
        if(arr[v[r]]<K)
        {
            arr[v[r]]++;
            r++;
            result = max(result, r - l);
        }
        else
        {
            arr[v[l]]--;
            l++;
        }
    }

    cout << result;


    return 0;
}