백준20922 문제 보러가기

문제

홍대병에 걸린 도현이는 겹치는 것을 매우 싫어한다. 특히 수열에서 같은 원소가 여러 개 들어 있는 수열을 싫어한다. 도현이를 위해 같은 원소가 $K$개 이하로 들어 있는 최장 연속 부분 수열의 길이를 구하려고 한다.

$100\,000$ 이하의 양의 정수로 이루어진 길이가 $N$인 수열이 주어진다. 이 수열에서 같은 정수를 $K$개 이하로 포함한 최장 연속 부분 수열의 길이를 구하는 프로그램을 작성해보자.

입력

첫째 줄에 정수 $N$ ($1 \le N \le 200\,000$)과
$K$ ($1 \le K \le 100$)가 주어진다.

둘째 줄에는 ${a_1, a_2, ... a_n}$이 주어진다 ($1 \le a_i \le 100\,000$)

출력

조건을 만족하는 최장 연속 부분 수열의 길이를 출력한다.

예제 입력 1

9 2
3 2 5 5 6 4 4 5 7

예제 출력 1

7

예제 입력 2

10 1
1 2 3 4 5 6 6 7 8 9

예제 출력 2

6

문제 해결 과정

일단 투포인터 문제는 left, right를 늘리면서 하는 방법이 대다수라고 생각한다.

이 문제도 그렇게 어려운 문제라고 생각은 하지 않았다.
left, right를 0으로 하고 right를 늘려가면서 딕셔너리에 넣고 해당 right 값의 개수가 K개가 넘는지 확인하면서 넘어가면 된다. 만약, K개가 넘으면 left 개수를 빼고 left 값을 늘려가면서 최대길이를 구하면 된다.

[3 2 5 5 6 4 4 5 7]가 있다고 가정하면, 처음에는 3..2..5..5..6.. 이런식으로 쌓는다. 아직 까지는 K가 2라고 가정했을 때 개수를 넘는 것이 없는데, 3..2..5..5..6..4..4..5에 다다를 때, left 값을 딕셔너리에서 빼고 left에 1을 더한다. 아직 까지 5가 줄어들지 않았기 때문에 다시 left 값(현재 2)을 빼고 다시 1을 더한다. 결국 5가 빠지면 right가 +1이 될 수 있다.

최종 코드

from collections import defaultdict

N, K = map(int, input().split())
l = list(map(int, input().split()))
left, right = 0, 0
dd = defaultdict(int)
cnt = 0

while(1) :
    if right == N :
        break
    if dd[l[right]] < K :
        dd[l[right]] += 1
        right += 1
    else :
        dd[l[left]] -= 1
        left += 1
    cnt = max(right-left, cnt)
    
print(cnt)