[Silver 1] 20922 겹치는 건 싫어
https://www.acmicpc.net/problem/20922
20922번: 겹치는 건 싫어
홍대병에 걸린 도현이는 겹치는 것을 매우 싫어한다. 특히 수열에서 같은 원소가 여러 개 들어 있는 수열을 싫어한다. 도현이를 위해 같은 원소가 $K$개 이하로 들어 있는 최장 연속 부분 수열
www.acmicpc.net
이 문제는 투 포인터를 통해 해결할 수 있다.
K의 값에 따라 연속 수열에 들어올 수 있는 같은 값의 개수가 달라진다.
예시에 있는 3 2 5 5 6 4 4 5 7은 K가 2이므로 수열에 같은 값이 2개 이하 존재해야한다.
즉, 3 2 5 5 6 4 4와 2 5 5 6 4 4, 5 5 6 4 4, 5 6 4 4 5 7, 6 4 4 5 7, ... 이 가능하다.
이중 가장 긴 수열의 길이는 7이므로 답은 7이 된다.
이 문제를 해결하기 위해 그림을 그려보면 아래와 같다.
step 1 (초기화)
element 배열
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 |
arr 배열
| 3(end)(start) | 2 | 5 | 5 | 6 | 4 | 4 | 5 | 7 |
result = 0
step 2
element 배열
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 0 | 0 | 1 | 0 | 0 | 0 | 0 |
arr 배열
| 3 (end) | 2 (start) | 5 | 5 | 6 | 4 | 4 | 5 | 7 |
result = 1
step 2
element 배열
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 0 | 1 | 1 | 0 | 0 | 0 | 0 |
arr 배열
| 3 (end) | 2 | 5 (start) | 5 | 6 | 4 | 4 | 5 | 7 |
result = 2
step 3
element 배열
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 0 | 1 | 1 | 0 | 1 | 0 | 0 |
arr 배열
| 3 (end) | 2 | 5 | 5 (start) | 6 | 4 | 4 | 5 | 7 |
result = 3
step 4
element 배열
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 0 | 1 | 1 | 0 | 2 | 0 | 0 |
arr 배열
| 3 (end) | 2 | 5 | 5 | 6 (start) | 4 | 4 | 5 | 7 |
result = 4
step 5
element 배열
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 0 | 1 | 1 | 0 | 2 | 1 | 0 |
arr 배열
| 3 (end) | 2 | 5 | 5 | 6 | 4 (start) | 4 | 5 | 7 |
result = 5
step 6
element 배열
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 0 | 1 | 1 | 1 | 2 | 1 | 0 |
arr 배열
| 3 (end) | 2 | 5 | 5 | 6 | 4 | 4 (start) | 5 | 7 |
result = 6
step 7
element 배열
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 0 | 1 | 1 | 2 | 2 | 1 | 0 |
arr 배열
| 3 (end) | 2 | 5 | 5 | 6 | 4 | 4 | 5 (start) | 7 |
result = 7
step 8
element 배열
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 0 | 1 | 0 | 2 | 2 | 1 | 0 |
arr 배열
| 3 | 2 (end) | 5 | 5 | 6 | 4 | 4 | 5 (start) | 7 |
result = 7
step 9
element 배열
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 0 | 0 | 0 | 2 | 2 | 1 | 0 |
arr 배열
| 3 | 2 | 5 (end) | 5 | 6 | 4 | 4 | 5 (start) | 7 |
result = 7
step 10
element 배열
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 0 | 0 | 0 | 2 | 1 | 1 | 0 |
arr 배열
| 3 | 2 | 5 | 5 (end) | 6 | 4 | 4 | 5 (start) | 7 |
result = 7
step 11
element 배열
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 0 | 0 | 0 | 2 | 2 | 1 | 0 |
arr 배열
| 3 | 2 | 5 | 5 (end) | 6 | 4 | 4 | 5 | 7 (start) |
result = 7
step 12
element 배열
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 0 | 0 | 0 | 2 | 2 | 1 | 1 |
arr 배열
| 3 | 2 | 5 | 5 (end) | 6 | 4 | 4 | 5 | 7 |
result = 7
위 과정을 코드로 변환하면 아래와 같다.
#include<iostream>
using namespace std;
int N, K;
int arr[200001];
int element[100001];
int result = 0;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> N >> K;
for (int i = 0; i < N; i++) {
cin >> arr[i];
}
int start = 0;
int end = 0;
while (start < N) {
if (element[arr[start]] != K) {
element[arr[start]]++;
start++;
}
else {
element[arr[end]]--;
end++;
}
result = max(result, start - end);
}
cout << result << '\n';
return 0;
}