▶ 실버 1 (투포인터)
풀이
N은 200,000 이하이기 때문에 시간 복잡도가 O(N^2)이 넘어가면 시간 초과가 발생합니다.
따라서 투포인터를 활용하여 O(N)의 시간 복잡도가 될 수 있도록 하였습니다.
투포인터 활용해서 start, end로 인덱스를 구간 관리하였습니다.
또한, 숫자 별 카운트는 Counter 라이브러리를 사용하였습니다.
구간 내에 k 초과한 개수를 가진 값이 있으면 안되기 때문에,
현재 값(end 인덱스의 값)의 개수과 k 값을 비교하여 두 가지 경우에 대한 처리를 합니다.
1) k보다 작다면, 해당 값을 구간에 추가해도 된다는 의미이기에
- counter 값을 증가시키고
- 구간의 개수와 최댓값을 비교하여 ans을 갱신하고
- end 인덱스를 증가시킵니다.
2) k보다 크거나 같으면, 해당 값을 구간에 추가하면 안된다는 의미이기에
- counter 값을 감소시키고
- start 인덱스를 증가시킵니다.
end 인덱스가 배열의 끝에 도달할 때까지 이 과정을 반복하여 답을 구합니다.
코드
# 20922_겹치는 건 싫어
from collections import Counter
import sys
input = sys.stdin.readline
n, k = map(int, input().split())
num_list = list(map(int, input().split()))
counter = Counter()
start, end = 0, 0
ans = 0
while end < n:
if counter[num_list[end]] < k:
counter[num_list[end]] += 1
ans = max(ans, end - start + 1)
end += 1
else:
counter[num_list[start]] -= 1
start += 1
print(ans)
'Algorithm > Baekjoon' 카테고리의 다른 글
15681_트리와 쿼리 (0) | 2025.03.12 |
---|---|
14502_연구소 (0) | 2025.03.07 |
11123_양 한마리... 양 두마리... (0) | 2025.03.07 |
15558_점프 게임 (0) | 2025.02.26 |
16719_ZOAC (0) | 2025.02.25 |