[알고리즘] 백준 - 겹치는 건 싫어

백준 - 겹치는 건 싫어

내 풀이

from collections import defaultdict

N, K = map(int, input().split())
arr = list(map(int, input().split()))

max_ans = 0
left, right = -1, 0
cur_nums = defaultdict(int)

def get_next_count(cur_nums, right):
    return cur_nums[arr[right]]+1 if cur_nums.values() else 0


while right < len(arr):
    while right < len(arr) and get_next_count(cur_nums, right) <= K:
        max_ans = max(max_ans, right - left)
        cur_nums[arr[right]] += 1
        right += 1

    while right < len(arr) and get_next_count(cur_nums, right) > K:
        left += 1
        cur_nums[arr[left]] -= 1

print(max_ans)

슬라이딩 윈도우 문제인데 역시나 인덱스 하나 차이로 오류가 계속 발생했다. 정형화된 패턴으로 문제를 풀 수 있게 준비해야하는데, 이번에 정한거는 left =0, right = 0에서 시작하고 right < len(arr)인 동안 반복하는 것이다.

다른 사람 풀이

import sys; inp = sys.stdin.readline

N, K = map(int, inp().split())
_list = list(map(int, inp().split()))

left = 0
right = 0
maxLen = 0
countArr = [0] * 100001

while right < N:
    if countArr[_list[right]] == K: # 지금 보는 원소의 갯수가 K개라면 left를 좁혀서 줄여본다
        countArr[_list[left]] -= 1
        left += 1
    else: # 지금 보는 원소의 갯수가 K개 보다 작다면 right를 늘려준다 
        maxLen = max(maxLen, right - left)
        countArr[_list[right]] += 1 # 나온 원수의 갯수를 세준다
        right += 1

print(maxLen + 1)

다른 사람들의 풀이는 대부분 left, right = 0, 0으로 시작하고 while right < len(arr) 형태다. 이 형태로 풀 수 있게 연습을 맞춰야 겠다.