[python] 백준 20922번 겹치는 건 싫어

백준 20922번 겹치는 건 싫어

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

문제

풀이

투포인터 너무 싫어...
투포인터라고 생각까지는 했다.
근데 생각에 오류가 있었다.
만약에 while temp[nlist[end]] > k: 어떤 숫자의 빈도가 k를 초과하면, start 를 하나 움직이는 것이 아니라 아예 end - 1로 가야한다고 생각했다.

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

start = 0
end = 0
temp = dict.fromkeys(nlist, 0)  # 수열의 각 숫자에 대한 빈도 카운트를 0으로 초기화

max_len = 0

while end < n:
    temp[nlist[end]] += 1  # 현재 end 위치의 숫자의 빈도 증가
    
    # 만약 어떤 숫자의 빈도가 k를 초과하면, start를 이동시켜야 함
    while temp[nlist[end]] > k:
        temp[nlist[start]] -= 1  # start 위치의 숫자의 빈도 감소
        start += 1  # start를 오른쪽으로 이동
    
    # 조건을 만족하는 부분 수열의 길이를 계산하여 최대 길이 갱신
    max_len = max(max_len, end - start + 1)
    
    end += 1  # end를 오른쪽으로 이동

print(max_len)

📌 주의

아직 멀었군 투포인터