20922_겹치는 건 싫어

▶ 실버 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)