백준 20922 : 겹치는 건 싫어 (Python)

본문 링크

import sys
input=sys.stdin.readline

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

L=list(map(int,input().split()))

start=0 ; end=1

A=[0]*100001

A[L[start]]+=1 ; count=1 ; answer=0
while end<N:
    if A[L[end]]<K:
        A[L[end]]+=1
        count+=1
        end+=1

    elif A[L[end]]>=K:
        A[L[start]]-=1
        start+=1
        count-=1
    answer=max(answer,count)

print(answer)

📌 어떻게 접근할 것인가?

같은 원소가 $K$ 이하인 최장 연속 부분 수열을 구하는 문제이다.

문제에서 주어지는 범위를 보면 $N$의 범위가 ($1 \le N \le 200\,000$) 이다.
따라서 이 문제는 가능하면 $O(N)$ 이하로 풀어야지 시간초과가 나지않는다.

따라서 모든 수를 탐색하고 $O(N)$으로 탐색가능한 투 포인터를 사용하기로 했다.

📌 어떻게 투포인터를 적용시킬것인가?

start=0 , end=1 로 잡는다. 그리고 A라는 배열을 100001개 만들어 준다.
따라서 A배열은 1부터 100000까지 $a_i$ 의 값의 개수를 저장하는 배열이 만들어 진다.

처음은 무조건 하나를 셀 수 있으므로 A[L[start]]+=1 , count=1 로 잡아준다.

이후 A[L[end]] ( L[end] 원소값의 개수) 가 $K$보다 작다면 A[L[end]] 를 1 증가시키고 end 를 증가시킨다.
만약 $K$ 보다 크거나 같으면 연속이 불가능하므로 앞의 start 를 증가시킨다.
그리고 count-=1 를 해준다. 따라서 start 값이 $K$ 보다 크거나 같은 값과 일치하면 다시 연속부분 수열이 증가한다.

또한 count 는 매번 유동적으로 변하기 때문에 answer 변수에 항상 값을 체크 해준다.

마지막으로 answer 를 출력한다.

✅ 코드에서 주의해야할 부분

• A 배열의 크기는 100001로 잡는다.
• while문 조건은 end<N으로 잡아준다. start=0 , end=1로 잡았기 때문이다.
• answer 값은 count값이 변하므로 매번 최대값을 체크해준다.
• 처음 count 값은 1로 잡고 A[L[start]]값 또한 1로 잡아준다.