[Python/파이썬] 백준 20922번 겹치는 건 싫어

20922번: 겹치는 건 싫어

 

문제

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

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

입력

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

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

출력

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

코드

from collections import defaultdict

n, k = map(int, input().split())
arr = list(map(int, input().split()))
    
start, end = 0, 0

max_length = 1
num_cnt = defaultdict(int)
while end < n:
    if num_cnt[arr[end]] < k:
        num_cnt[arr[end]] += 1
        end += 1
    else:
        num_cnt[arr[start]] -= 1
        start += 1
    max_length = max(max_length, end-start)
print(max_length)

• num_cnt라는 defaultdict에 arr[start:end+1] 배열에서 숫자들의 등장 횟수를 저장해놓는다.
• 지금 end 인덱스에 있는 숫자의 등장 횟수가 아직 k번 미만이라면 end를 증가시킨다. 왜 end 인덱스의 값이 등장한 횟수만 보냐면 어차피  새로 추가된 것은 end 뿐이다. 이전에 다른 원소가 k번 초과로 등장했다면 이미 그 원소가 end 인덱스에 해당할 때 else 조건에서 걸렸을 것이다.
• end 인덱스의 원소의 등장 횟수가 k번 이상이라면 start를 하나씩 줄이며 배열의 크기를 점점 줄여본다. 그러다가 end 인덱스 원소의 등장 횟수가 감소하여 k번 미만이 된다면 다시 end 인덱스를 증가시키며 배열의 크기를 점점 키워보면 된다.