728x90
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;
}
728x90
'알고리즘 문제 > 슬라이싱 윈도우' 카테고리의 다른 글
[개쉬운 풀이] 프로그래머스 - 연속된 부분 수열 JAVA (0) | 2025.05.12 |
---|---|
[개쉬운 풀이] 백준 2531 회전 초밥 (0) | 2024.07.30 |