[백준 20922 / Python / 실버1] 겹치는 건 싫어

문제

 

슬라이딩 윈도우 or 투 포인터 문제이다. 나는 슬라이딩 윈도우가 익숙하고 더 직관적이라고 생각해서, 슬라이딩 윈도우 방식으로 풀었다.

 

from collections import defaultdict

import sys

input = sys.stdin.readline

"""

최장 연속 부분 수열 길이 구하기

같은 정수는 K개 까지 허용

N: 제공된 수열 길이

K: 같은 정수 허용 상한

nums: 제공된 수열

num_count: 각 숫자 당 개수 세는 딕셔너리, 기본값 int

슬라이딩 윈도우

딕셔너리 구조 -> 숫자: 개수

-> 특정 숫자가 K개가 넘었다면,

    left는 특정 숫자 위치까지 진행하며 딕셔너리에서 값을 빼고

    right는 right + 1

    부분부터 다시 진행한다

"""

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

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

num_count = defaultdict(int)

left = 0

right = 0

result = 0

count = 0

while left <= right and right < N:

   

    num_count[nums[right]] += 1

    if num_count[nums[right]] > K:  # 중복 횟수 초과 시

        # left를 하나씩 올리면서 숫자당 개수 줄이기

        for i in range(left, N - 1):

            num_count[nums[i]] -= 1

            left += 1

            if nums[i] == nums[right]:

                break

   

    count = (right - left) + 1

    result = max(result, count)

    right += 1

print(result)

 

N이 10만이기 때문에 완전탐색으로 진행하면 시간복잡도가 O(N^2) 이고 10만 * 10만으로 100억번 연산이 나오기 때문에 문제를 해결할 수 없다. 슬라이딩 윈도우 방식으로 하면 약 O(2N) 정도로, 즉 O(N)에 해결할 수 있다.

 

해결방법은 간단하다. defaultdict를 활용해서, 각 숫자 당 카운트를 저장해 두고, right를 1씩 늘려가며 숫자 당 카운트를 집계하며 동시에 count변수로 최장길이를 구한다. 

 

이 때 만약 특정 숫자 값이 K를 넘어서면, for문이 동작한다. 해당 K 위치까지 left 좌표를 1씩 올려가며, dict에서 숫자들의 카운트를 빼 준다. while문을 써도 되긴 하는데, 나는 무한루프 방어 목적으로 for문을 활용했다.

 

테스트 코드를 예로 들어 보겠다. 아래와 같은 조건에서, 굵게 표시된 곳까지 진행했고 count는 7이라고 하자.

3 2 5 5 6 4 4 5 7

left = 0, right = 6

 

여기서 right가 1 증가하면 5의 카운트가 3이 되고, K:2 보다 커지게 된다.

3 2 5 5 6 4 4 5 7

left = 0, right = 7

 

5의 카운트가 초과되었으므로, left를 5 다음 자리까지 올려 준다.

3 2 5 5 6 4 4 5 7

left = 3, right = 7

 

이렇게 K를 넘을 때마다 left를 올려 가며 right가 N에 도달할 때까지 진행해주면 된다. count는 직접 하나씩 증가시킬 필요 없이, (right - left) + 1 연산이 현재 수열 길이를 리턴하므로 이걸 활용하면 된다. 근데 사실 count 변수 없이 연산만으로도 짤 수 있긴 한데, 가독성을 위해 count 변수를 명시적으로 사용했다.

 

결과

 

푸는데 1시간 조금 넘게 걸렸다. 이젠 문제를 보고 자연스럽게 알고리즘이 떠오를 수준은 되었지만, 여전히 구현력이 부족하다. 머리속에 맴도는 해결방법을 실제 코드로 옮기는 게 아직 좀 느리다. 열심히 반복훈련 하는 수 밖에 없을 것 같다.