파이썬(Python)으로 k개 요소 제거 후 최소 진폭 구하는 방법

문제 개요

숫자 리스트 nums와 정수 k가 주어졌을 때, nums에서 k개의 요소를 제거한 뒤 남은 숫자들의 (최댓값 − 최솟값), 즉 진폭(amplitude)이 최소가 되도록 만드는 문제입니다.

예를 들어 입력이 nums = [4, 10, 3, 2, 8, 9], k = 3이라면 출력은 2가 됩니다. 10, 8, 9를 제거하면 남은 숫자는 [4, 3, 2]이며, 이때 최댓값은 4, 최솟값은 2이므로 차이는 2가 됩니다.

해결 접근 방법

이 문제는 정렬과 슬라이딩 윈도우 기법을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

• 리스트 nums를 오름차순으로 정렬합니다.
• k개의 요소를 제거하면 남는 요소의 개수는 p = len(nums) − k개입니다.
• 정렬된 배열에서 길이가 p인 연속 구간(윈도우) 중 양 끝 값의 차이가 가장 작은 구간을 찾습니다.
• 해당 구간의 (마지막 값 − 첫 번째 값)이 곧 최소 진폭이 됩니다.

즉, 큰 값들과 작은 값들을 제거하여 극단적인 값을 없애는 것이 아니라, 정렬 후 인접한 구간만 비교하면 되기 때문에 모든 조합을 검사할 필요가 없습니다.

알고리즘 단계

1. nums를 정렬합니다.
2. p := len(nums) − k로 설정합니다.
3. m := 마지막 요소 − nums[0]으로 초기화합니다.
4. i를 0부터 len(nums) − p까지 반복하면서, nums[i + p − 1] − nums[i]가 m보다 작으면 m을 갱신합니다.
5. m을 반환합니다.

구현 예제

아래 파이썬 코드를 통해 더 자세히 이해할 수 있습니다.

def solve(nums, k):
   nums = sorted(nums)
   p = len(nums) - k
   m = nums[-1] - nums[0]
   for i in range(0, len(nums) - p + 1):
      if nums[i + p - 1] - nums[i] < m:
         m = nums[i + p - 1] - nums[i]
   return m

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

입력

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

출력

2

시간 복잡도

정렬에 O(n log n)의 시간이 소요되고, 슬라이딩 윈도우 탐색에는 O(n)의 시간이 소요되므로 전체 시간 복잡도는 O(n log n)입니다. 공간 복잡도는 정렬에 사용되는 O(n)입니다.