[개쉬운 풀이] 백준 20922 겹치는 건 싫어 (2일차)

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

 

문제

 

생각

1. 현재 위치부터 최장 연속 부분 수열을 찾는다.

2. 조건에 부합하지 않는 부분이 나온다면 앞 부분을 삭제하고 다시 최장 부분 연속 부분 수열을 찾는다.

-> 슬라이싱 윈도우

 

풀이

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

int N, K;
vector<int> v;
vector<int> isVisited(100001);

void input(){
    cin >> N >> K;
    v = vector<int> (N);
    
    for(int i = 0; i < N; i++){
        cin >> v[i];
    }
}

void sol(){
    int start = 0, end = 0;
    int answer = 0;
    //슬라이딩 윈도우
    for(start = 0; start < N; start++){
        //갈 수 있는 최대 배열
        while(end < N && isVisited[v[end]] < K){
            isVisited[v[end++]]++;
        }
        answer = max(answer, end - start);
        isVisited[v[start]]--;
    }
    cout << answer ;
}

int main(){
    input();
    sol();
    return 0;
}