[ BOJ ] 20922 : 겹치는 건 싫어 ( SILVER 1 ) / Python

>> 문제 바로가기 (https://www.acmicpc.net/problem/20922)

문제

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

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

입력

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

둘째 줄에는 a_1, a_2, ... a_n이 주어진다 (1 ≤ a_i ≤ 100 000)

출력

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

풀이 과정

투 포인터를 이용하여 같은 정수를 K개 이하로 포함한 최장 연속 부분 수열의 길이를 구한다.

import sys
input = sys.stdin.readline

n, k = map(int, input().rstrip().split())
arr = list(map(int, input().rstrip().split()))

start = 0
end = 1
now = {i:0 for i in range(1, 100001)}

now[arr[0]] = 1
result = 0
while n >= end:
    result = max(result, end - start)
    if n == end: break
    if n > end and now[arr[end]] < k:
        now[arr[end]] += 1
        end += 1
    else:
        while now[arr[end]] >= k and start < end - 1:
            now[arr[start]] -= 1
            start += 1
        if start == end - 1:
            now[arr[start]] -= 1
            start += 1
            now[arr[end]] += 1
            end += 1

print(result)