Python으로 길이 K인 부분 리스트를 제거한 후 최소 진폭 구하기

문제 개요

숫자로 이루어진 리스트 nums와 값 k가 주어졌다고 가정해 보겠습니다. 먼저 길이가 k인 부분 리스트(sublist)를 하나 제거한 뒤, 남은 원소들의 최댓값에서 최솟값을 뺀 값, 즉 진폭(amplitude)이 최소가 되도록 만드는 것이 목표입니다.

예를 들어 입력이 nums = [2, 3, 10, 9, 8, 4], k = 3이라면 결과는 2가 됩니다. 가운데의 [10, 9, 8]을 제거하면 [2, 3, 4]만 남고, 최댓값 4에서 최솟값 2를 빼면 2가 되기 때문입니다.

해결 접근 방법

모든 제거 위치마다 최댓값과 최솟값을 매번 새로 계산하면 비효율적입니다. 대신 접두사(prefix) 배열과 접미사(suffix) 배열을 활용하면 O(N) 시간 안에 효율적으로 해결할 수 있습니다.

구체적인 단계는 다음과 같습니다.

• N := nums의 길이

• nums를 lmin과 lmax에 복사합니다. (왼쪽 끝부터 각 인덱스까지의 최솟값·최댓값 저장용)

• 같은 방식으로 nums를 rmin과 rmax에도 복사합니다. (오른쪽 끝부터의 최솟값·최댓값 저장용)

• i를 1부터 N-1까지 순회하며 다음을 수행합니다.

  • lmin[i] := lmin[i]와 lmin[i - 1] 중 작은 값

  • lmax[i] := lmax[i]와 lmax[i - 1] 중 큰 값

• i를 N-2부터 0까지 감소시키며 다음을 수행합니다.

  • rmin[i] := rmin[i]와 rmin[i + 1] 중 작은 값

  • rmax[i] := rmax[i]와 rmax[i + 1] 중 큰 값

• ans := (rmax[k] - rmin[k])와 (lmax[~k] - lmin[~k]) 중 작은 값으로 초기화합니다. 여기서 ~k는 파이썬의 비트 반전 연산자로, 뒤에서 k번째 인덱스를 의미합니다.

• i를 0부터 N-k-2까지 순회하며 다음을 수행합니다.

  • cand := max(lmax[i], rmax[i + k + 1]) - min(lmin[i], rmin[i + k + 1]) — 즉, i+1부터 i+k까지의 구간을 제거했을 때의 진폭

  • ans := ans와 cand 중 작은 값

• ans를 반환합니다.

예제 코드

아래 구현을 통해 더 자세히 이해해 보겠습니다.

def solve(nums, k):
    N = len(nums)
    lmin, lmax = nums[:], nums[:]
    rmin, rmax = nums[:], nums[:]
    for i in range(1, N):
        lmin[i] = min(lmin[i], lmin[i - 1])
        lmax[i] = max(lmax[i], lmax[i - 1])
    for i in range(N - 2, -1, -1):
        rmin[i] = min(rmin[i], rmin[i + 1])
        rmax[i] = max(rmax[i], rmax[i + 1])

    ans = min(rmax[k] - rmin[k], lmax[~k] - lmin[~k])
    for i in range(N - k - 1):
        cand = max(lmax[i], rmax[i + k + 1]) - min(lmin[i], rmin[i + k + 1])
        ans = min(ans, cand)

    return ans

nums = [2, 3, 10, 9, 8, 4]
k = 3
print(solve(nums, k))

입력

[2, 3, 10, 9, 8, 4], 3

출력

2

정리

이 알고리즘은 왼쪽 누적 최솟값·최댓값 배열(lmin, lmax)과 오른쪽 누적 최솟값·최댓값 배열(rmin, rmax)을 미리 계산해 두므로, 각 제거 위치에 대해 상수 시간 O(1)만에 해당 경우의 진폭을 구할 수 있습니다. 전체 시간 복잡도는 O(N), 공간 복잡도 역시 O(N)으로, 리스트가 클 때도 효율적으로 동작합니다.