[BOJ/Python] 20922번 : 겹치는 건 싫어

https://www.acmicpc.net/problem/20922

문제

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

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

입력

출력

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

---

구상

우선 숫자의 범위가 100000이므로 100001짜리 배열을 만들어 count를 셀 것이다. 이 카운트를 안넘는다면, end라는 포인터를 오른쪽으로 옮기고, 만약 카운트가 넘어가면 start를 옮기며 count가 안넘게 조정하여, len을 구하면 될 거 같다

코드

n,k = map(int,input().split())
arr=list(map(int,input().split()))
count=[0 for _ in range(100001)]
ml=0
start,end=0,0


while end < n:
    if count[arr[end]] < k:
        count[arr[end]] += 1
        end += 1
        ml = max(ml, end - start)
    else:
        count[arr[start]] -= 1
        start += 1
        
        
print(ml)