[Coding Test][Python][백준] BOJ #20922 겹치는 건 싫어

 

 

#20922 겹치는 건 싫어

문제)

홍대병에 걸린 도현이는 겹치는 것을 매우 싫어한다. 특히 수열에서 같은 원소가 여러 개 들어 있는 수열을 싫어한다. 도현이를 위해 같은 원소가 K$K$개 이하로 들어 있는 최장 연속 부분 수열의 길이를 구하려고 한다.

 $100\,000$ 이하의 양의 정수로 이루어진 길이가 $N$인 수열이 주어진다.  이 수열에서 같은 정수를 $K$개 이하로 포함한 최장 연속 부분 수열의 길이를 구하는 프로그램을 작성해보자.

입력)

첫째 줄에 정수 $N$ ($1 \le N \le 200\,000$)과 $K$ ($1 \le K \le 100$)가 주어진다.

둘째 줄에는 ${a_1, a_2, ... a_n}$이 주어진다 ($1 \le a_i \le 100\,000$)

출력)

조건을 만족하는 최장 연속 부분 수열의 길이를 출력한다.

---

풀이)

※ 풀이 아이디어

Two Pointer(Sliding Window)를 적용한다면 쉽게 해결할 수 있는 문제입니다.
1. start, end Pointer를 사용하여 Window를 유지
2. end Pointer를 이용하면서 연속 수열이 되는지 확인
3. 연속 수열 조건을 만족하지 않는다면 start  Pointer를 이동시켜 조건을 만족하도록 유지

# 투 포인터
N, K = map(int, input().split())

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

start = 0
max_len = 0 
num_count = dict().fromkeys(list(range(1, max(arr)+1)), 0)

for end in range(N):
	# end Pointer를 계속해서 이동시킨다
    num_count[arr[end]] += 1
    
	# 조건을 만족하지 않을 때
    while num_count[arr[end]] > K:
        num_count[arr[start]] -= 1
        start += 1
	# 이동할 때마다 최대 길이 갱신
    max_len = max(max_len, end - start + 1)

print(max_len)

 

위의 풀이 과정을 이해하기 쉽게 그림으로 그려보면 아래 그림과 같은 과정을 통해 수행됩니다.

 

Input Array는 문제의 첫 번째 Input 예제에서 이해가 더 잘 되도록 임의로 추가한 것입니다.(N=12 K=2)

for loop의 처음 진입했을때의 상태입니다.

다음 loop의 상태입니다.

현재 while문의 조건을 만족하는 상태이므로 계속 for문을 돌며 end Pointer를 이동시킵니다.

end Pointer가 3번째 5를 만났을 때의 상황입니다.

이 때는 while문의 조건을 만족하지 않아 start Pointer를 한칸씩 이동시키면서 num_count 딕셔너리의 값에 -1을 해서 움직입니다.

array의 첫번째 5를 지난다면 while문의 조건을 만족하게 되어서 while문을 탈출하고 max_len을 갱신하게 됩니다.