백준 20922 겹치는 건 싫어 Python

🐸 문제 정보

20922번: 겹치는 건 싫어

 

🤖 알고리즘

투포인터

 

⏱️ 풀이 시간

15.53m

 

📝 풀이

비교적 간단한 투포인터 문제였다.

마지막까지 전부 통과한 경우에 길이를 출력하는 것을 잊어 약간의 시간이 더 걸렸다.

1. start와 end 모두 0부터 시작
2. end를 하나씩 뒤로 이동하며 딕셔너리에 담기
3. end 인덱스에 해당하는 숫자의 개수가 k보다 많다면, 우선 end - start를 res와 비교하여 더 큰 값 넣기
4. start를 뒤로 하나씩 이동하며 딕셔너리에서 해당 인덱스의 숫자를 빼줌
   • 이 때 딕셔너리[end]에 해당하는 값의 개수가 k개 이하가 되면 탈출
5. 마지막에 end - start와 반복문 돌며 갱신해놓은 res, 둘 중 큰 값을 출력

 

🧑‍💻 나의 답

# pypy3

import sys
input = sys.stdin.readline

n, k = list(map(int, input().rstrip().split()))
nums = list(map(int, input().rstrip().split()))
num_dict = {}

s, e = 0, 0
res = 0
while e != n:
    num_dict[nums[e]] = num_dict.get(nums[e], 0) + 1
    if num_dict.get(nums[e], 0) > k:
        res = max(res, e - s)
        while (s <= e) and (num_dict.get(nums[e], 0) > k):
            num_dict[nums[s]] -= 1
            s += 1
    e += 1

print(max(res, e - s))