문제 개요
정렬되지 않은 배열이 주어졌을 때, 정렬된 상태에서 인접한 두 요소 사이의 최대 차이(최대 간격)를 구하는 문제입니다. 배열에 포함된 요소가 2개 미만이라면 0을 반환합니다.
예를 들어 배열이 [12, 3, 9, 1, 17]이라면, 정렬한 결과는 [1, 3, 9, 12, 17]이 됩니다. 이때 인접 요소 간의 차이는 각각 2, 6, 3, 5이므로 최대 간격은 6입니다.
접근 방법: 버킷(Bucket) 활용
단순히 배열을 정렬한 뒤 인접 요소의 차이를 비교하면 O(n log n)의 시간이 필요합니다. 하지만 버킷을 이용하면 정렬 없이도 O(n) 시간에 문제를 해결할 수 있습니다.
핵심 아이디어는 다음과 같습니다. 최솟값과 최댓값 사이를 (n−1)개의 균등한 구간(버킷)으로 나누면, 최대 간격은 반드시 서로 다른 버킷에 속한 값들 사이에서 발생합니다. 따라서 각 버킷에는 해당 구간의 최솟값과 최댓값만 저장하고, 인접한 버킷 사이의 간격만 비교하면 됩니다.
알고리즘 단계
- minVal은 양의 무한대(+∞), maxVal은 음의 무한대(−∞)로 초기화합니다.
- n을 배열 nums의 크기로 설정합니다.
- n이 2보다 작으면 0을 반환합니다.
- 배열 전체를 순회하며 minVal과 maxVal을 갱신합니다.
- gap := ceil((maxVal − minVal) / (n − 1))로 버킷 하나의 폭을 계산합니다.
- 크기가 (n − 1)인 bucketMax 배열을 만들고 −∞로 채웁니다.
- 크기가 (n − 1)인 bucketMin 배열을 만들고 +∞로 채웁니다.
- 배열을 다시 순회하며 다음을 수행합니다.
- x := nums[i]
- x가 minVal 또는 maxVal이면 해당 반복은 건너뜁니다.
- idx := (nums[i] − minVal) / gap으로 버킷 인덱스를 계산합니다.
- bucketMax[idx] := max(bucketMax[idx], nums[i])
- bucketMin[idx] := min(bucketMin[idx], nums[i])
- ret := 0, prev := minVal로 초기화합니다.
- 버킷을 순회하며 다음을 수행합니다.
- 해당 버킷이 비어 있으면(bucketMax[i] = −∞이고 bucketMin[i] = +∞) 건너뜁니다.
- ret := max(ret, bucketMin[i] − prev)
- prev := bucketMax[i]
- 최종적으로 max(ret, maxVal − prev)를 반환합니다.
C++ 구현 예제
아래 구현을 통해 더 자세히 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
int maximumGap(vector<int>& nums) {
lli minVal = INT_MAX;
lli maxVal = INT_MIN;
int n = nums.size();
if(n < 2) return 0;
for(int i = 0; i < n; i++){
minVal = min((lli)nums[i], minVal);
maxVal = max((lli)nums[i], maxVal);
}
int gap = ceil((double)(maxVal - minVal) / (double)(n - 1));
vector <int> bucketMax(n - 1, INT_MIN);
vector <int> bucketMin(n - 1, INT_MAX);
for(int i = 0; i < n; i++){
int x = nums[i];
if(x == minVal || x == maxVal) continue;
int idx = (nums[i] - minVal) / gap;
bucketMax[idx] = max(bucketMax[idx], nums[i]);
bucketMin[idx] = min(bucketMin[idx], nums[i]);
}
lli ret = 0;
lli prev = minVal;
for(int i = 0; i < n - 1; i++){
if(bucketMax[i] == INT_MIN && bucketMin[i] == INT_MAX) continue;
ret = max(ret, bucketMin[i] - prev);
prev = bucketMax[i];
}
return max(ret, maxVal - prev);
}
};
main(){
Solution ob;
vector<int> v = {12,3,9,1,17};
cout << (ob.maximumGap(v));
}
실행 결과
입력:
[12,3,9,1,17]
출력:
6
복잡도 분석
이 알고리즘은 배열을 세 번 순회하므로 시간 복잡도는 O(n)이며, 버킷 두 개를 저장해야 하므로 공간 복잡도 역시 O(n)입니다. 일반적인 정렬 기반 풀이(O(n log n))보다 빠르게 동작한다는 점이 이 방식의 가장 큰 장점입니다.