[백준] 20922번 겹치는 건 싫어

문제: 20922번: 겹치는 건 싫어

basic-algo-lecture/workbook/0x14.md at master · encrypted-def/basic-algo-lecture

basic-algo-lecture/workbook/0x14.md at master · encrypted-def/basic-algo-lecture

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <limits>

using namespace std;

int counts[100001]; // 0번 인덱스 안 써

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

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

    int st = 0;
    int en = 0;
    int tmpLen = 0;
    int ans = -1;
    while (en < n) {
        // 야 이미 해당 숫자가 k 번 이상 등장했어? 그럼 아닐때까지 st 늘랴..
        while (counts[nums[en]] >= k) {
            counts[nums[st]]--; // st 를 증가시키니까 앞에 수 버림
            tmpLen--;
            st++;
        }
        tmpLen++;
        counts[nums[en]]++; // 카운트 해줭
        en++;
  
        if (ans < tmpLen) {
            ans = tmpLen;
        }
    }
    cout << ans;

    return 0;
}

 

그냥 현재 추가하려고 하는 숫자가 이미 k 번 이상 등장했다면 st 값을 늘리도록 했다.