투포인터 | BOJ 백준 20922번 겹치는 건 싫어 | Python


created_at : 02 April 2024 - 2 mins read time
Tags: 투포인터

Table of Contents


BOJ 백준 20922번 겹치는 건 싫어 | Python

📌 백준 20922번 문제 바로가기

🔎 문제 설명

🩶 실버 1

- 난이도 ★☆☆☆
- 투포인터

처음엔 count 메소드나 Counter 라이브러리를 가져와서 중복되는 수의 개수를 세어줄까 했지만, 시간 초과 의 문제가 발생한다.
그래서 연속 구간의 시작과 끝을 움직이면서, 끝쪽에 있는 수의 개수를 조절해가면서 풀도록 설계하였다. 실버 1이었지만 투포인터를 생각해낸다면 체감 상으로는 훨씬 쉬웠던 문제였다. 코드는 다음과 같다.



💻 내 코드

import sys
input = sys.stdin.readline

from collections import defaultdict

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

end = 0
max_len = 0
cnt = 0

for start in range(N):
    while end < N:
        now = arr[end]
        if cnt_dict[now] + 1 > K: 
            break
        cnt_dict[now] += 1
        end += 1
        max_len = max(max_len, end - start)
    cnt_dict[arr[start]] -= 1

print(max_len)




 

💙 You need to log in to GitHub to write comments. 💙
If you can't see comments, please refresh page(F5).