오름차순으로 정렬된 숫자 리스트 nums가 주어졌다고 가정해 봅시다. 이 리스트에서 k개의 값을 삭제하여, 남은 값들 중 인접한 두 값의 차이가 가장 커지는 경우(인접 값 차이의 최댓값)가 가능한 한 작아지도록 만들어야 합니다. 최종적으로 그 최소화된 차이를 구하는 것이 목표입니다.
예를 들어 입력이 nums = [15, 20, 30, 400, 1500]이고 k = 2라면 출력은 10이 됩니다. 400과 1500을 제거하면 [15, 20, 30]이 남고, 인접한 값들의 차이는 각각 5와 10이므로 최대 차이는 10입니다.
풀이 접근 방법
이 문제는 동적 계획법(DP)으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다. 정렬된 배열에서 내부에 있는 요소를 삭제하면 두 개의 작은 차이가 하나의 더 큰 차이로 합쳐지기 때문에, 오히려 손해입니다. 따라서 최적의 전략은 항상 배열의 양쪽 끝에서 값을 삭제하는 것이며, 재귀적으로 어느 쪽 끝을 제거할지 선택하며 최적해를 탐색합니다.
구체적인 해결 단계는 다음과 같습니다.
- abs_diff := nums에서 연속된 두 요소 간의 차이를 모두 저장한 리스트를 만듭니다.
- dp(i, j, cnt) 함수를 정의합니다. 여기서 i와 j는 현재 고려 중인 abs_diff의 범위, cnt는 아직 사용 가능한 삭제 횟수입니다.
- cnt가 0이라면 더 이상 삭제할 수 없으므로, 범위 [i, j] 내 차이의 최댓값을 반환합니다.
- m := 0으로 초기화
- k를 i부터 j까지 반복하며 m := m과 abs_diff[k] 중 더 큰 값으로 갱신
- 그렇지 않다면 왼쪽 끝 차이를 제거하는 경우 dp(i + 1, j, cnt − 1)와 오른쪽 끝 차이를 제거하는 경우 dp(i, j − 1, cnt − 1) 중 더 작은 값을 반환합니다.
- 메인 메서드에서는 dp(0, abs_diff의 길이 − 1, k)를 반환합니다.
구현 예시
아래 코드를 통해 더 잘 이해해 보겠습니다.
class Solution:
def solve(self, nums, k):
abs_diff = [nums[i] - nums[i - 1] for i in range(1, len(nums))]
def dp(i, j, cnt):
if cnt == 0:
m = 0
for k in range(i, j + 1):
m = max(m, abs_diff[k])
return m
return min(dp(i + 1, j, cnt - 1), dp(i, j - 1, cnt - 1))
return dp(0, len(abs_diff) - 1, k)
ob = Solution()
nums = [15, 20, 30, 400, 1500]
k = 2
print(ob.solve(nums, k))
입력
[15, 20, 30, 400, 1500], 2
출력
10
동작 원리 정리
위 코드는 먼저 인접한 값들 사이의 차이만으로 이루어진 새로운 리스트를 만든 후, 삭제 횟수 k만큼 재귀적으로 왼쪽 또는 오른쪽 끝의 차이를 하나씩 걷어내며 진행합니다. 삭제를 모두 사용하면 남은 차이들 중 최댓값을 계산하고, 모든 분기 경로 중 최솟값이 곧 정답이 됩니다. 시간 복잡도는 재귀 호출마다 두 갈래로 나뉘므로 대략 O(k · 2^k) 수준이며, 필요에 따라 메모이제이션을 적용하면 성능을 더 개선할 수 있습니다.