숫자 리스트 nums가 주어졌을 때, 어떤 숫자와 그보다 작은 다음 숫자 사이에 존재하는 최대 차이를 구하는 문제입니다. 핵심 목표는 이 문제를 선형 시간 O(n) 안에 해결하는 것입니다.
예를 들어 입력이 nums = [14, 2, 6, 35, 12]라면 출력은 21이 됩니다. 35와 14 사이의 차이인 21이 가장 크기 때문입니다.
접근 방법: 버킷(Bucket) 기법 활용
단순히 정렬한 뒤 인접한 두 수의 차이를 비교하면 O(n log n)이 걸립니다. 하지만 버킷 정렬과 비둘기집 원리(Pigeonhole Principle)를 활용하면 정렬 없이도 선형 시간에 답을 구할 수 있습니다.
최대 차이는 최솟값과 최댓값의 범위를 n-1개 구간으로 나눈 값(delta)보다 항상 크거나 같으므로, 같은 버킷 내부에서는 최대 차이가 발생할 수 없습니다. 따라서 각 버킷의 최솟값과 이전 버킷의 최댓값만 비교하면 됩니다.
알고리즘 단계
max_val:= nums의 최댓값,min_val:= nums의 최솟값- 만약
max_val과min_val이 같다면(모든 원소가 동일하면) 0을 반환합니다. delta:= (max_val − min_val) / (nums의 길이 − 1) → 버킷 하나의 크기min_map:= 빈 맵 (값이 없으면 inf 반환)max_map:= 빈 맵 (값이 없으면 -inf 반환)res:= 0,idx:= 0으로 초기화- nums의 각
num에 대해:idx:= floor((num − min_val) / delta)max_map[idx]:= max_map[idx]와 num 중 큰 값min_map[idx]:= min_map[idx]와 num 중 작은 값
prev:= min_val로 설정- i를 0부터 nums의 길이 − 1까지 반복:
min_map[i]가 inf가 아니라면:res:= res와 (min_map[i] − prev) 중 큰 값prev:= max_map[i]
res를 반환합니다.
구현 예제
아래 코드를 통해 더 자세히 이해해 보겠습니다.
from collections import defaultdict
import math
class Solution:
def solve(self, nums):
max_val = max(nums)
min_val = min(nums)
if max_val == min_val:
return 0
delta = (max_val - min_val) / (len(nums) - 1)
min_map = defaultdict(lambda: float("inf"))
max_map = defaultdict(lambda: float("-inf"))
res = 0
idx = 0
for num in nums:
idx = math.floor((num - min_val) / delta)
max_map[idx] = max(max_map[idx], num)
min_map[idx] = min(min_map[idx], num)
prev = min_val
for i in range(len(nums)):
if min_map[i] != float("inf"):
res = max(res, min_map[i] - prev)
prev = max_map[i]
return res
ob = Solution()
nums = [14, 2, 6, 35, 12]
print(ob.solve(nums))입력
[14, 2, 6, 35, 12]
출력
21
정리
이 방법은 리스트를 한 번 순회하며 각 숫자를 버킷에 분배하고, 다시 한 번 버킷을 순회하며 인접 버킷 간의 차이를 계산하므로 전체 시간 복잡도는 O(n), 공간 복잡도 역시 O(n)입니다. 정렬이 필요 없기 때문에 데이터 크기가 클 때 특히 효율적입니다.