k개의 서로 다른 리스트가 주어졌다고 가정해 보겠습니다. 각 리스트의 요소는 오름차순으로 정렬되어 있습니다. 이때 k개의 리스트 각각에서 최소 한 개 이상의 숫자를 포함하는 가장 작은 범위를 찾아야 합니다.
여기서 범위 [a, b]가 범위 [c, d]보다 작다는 것은 다음 조건 중 하나를 만족하는 경우입니다.
- b - a < d - c 인 경우
- b - a == d - c 이면서 a < c 인 경우
예를 들어 입력이 [[4,10,15,25,26], [0,9,14,20], [5,18,24,30]]이라면, 세 리스트에서 각각 15, 14, 18을 선택할 수 있으므로 출력은 [14, 18]이 됩니다.
문제 해결 접근 방법
이 문제는 최소 힙(min-heap)을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 각 리스트에서 현재 가리키고 있는 원소들 중 최솟값과 최댓값의 차이를 계속 추적하면서, 최솟값이 속한 리스트의 포인터를 앞으로 이동시켜 더 좁은 범위를 찾는 것입니다.
구체적인 알고리즘 단계는 다음과 같습니다.
minRange := inf, maxRange := -inf, rangeSize := inf, tempMinRange := inf, tempMaxRange := -inf 로 초기화합니다.
n := nums의 크기로 설정합니다.
크기가 n인 포인터 배열 pointers를 정의합니다.
우선순위 큐 pq를 생성합니다.
i := 0부터 i < n까지 반복합니다.
{ nums[i][0], i } 쌍을 pq에 삽입합니다.
tempMaxRange := tempMaxRange와 nums[i][0] 중 최댓값으로 갱신합니다.
while 무한 루프를 수행합니다.
쌍 temp := pq의 top(최솟값)을 가져옵니다.
pq에서 해당 요소를 제거(pop)합니다.
tempMinRange := temp.first로 설정합니다.
idx := temp.second로 설정합니다.
만약 tempMaxRange - tempMinRange < rangeSize라면 다음을 수행합니다.
rangeSize := tempMaxRange - tempMinRange
minRange := tempMinRange
maxRange := tempMaxRange
pointers[idx]를 1 증가시킵니다.
만약 pointers[idx]가 nums[idx]의 크기와 같다면 루프를 종료합니다.
그렇지 않다면 다음을 수행합니다.
tempMaxRange := tempMaxRange와 nums[idx][pointers[idx]] 중 최댓값으로 갱신합니다.
{ nums[idx][pointers[idx]], idx } 쌍을 pq에 삽입합니다.
크기가 2인 배열 ans를 정의합니다.
ans[0] := minRange, ans[1] := maxRange로 설정합니다.
ans를 반환합니다.
이 알고리즘의 시간 복잡도는 전체 원소 개수를 N이라 할 때 O(N log k)이며, 공간 복잡도는 O(k)입니다. 힙에는 항상 k개의 원소만 유지되기 때문입니다.
예제 구현
아래 C++ 구현을 통해 더 잘 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
struct Comparator{
bool operator() (pair <int, int> a, pair <int, int> b){
return !(a.first < b.first);
}
};
class Solution {
public:
vector<int> smallestRange(vector<vector<int>>& nums) {
int minRange = INT_MAX;
int maxRange = INT_MIN;
int rangeSize = INT_MAX;
int tempMinRange, tempMaxRange, tempRangeSize;
tempMinRange = INT_MAX;
tempMaxRange = INT_MIN;
int n = nums.size();
vector <int> pointers(n);
priority_queue < pair <int, int>, vector < pair <int, int> >, Comparator > pq;
for(int i = 0; i < n; i++){
pq.push({nums[i][0], i});
tempMaxRange = max(tempMaxRange, nums[i][0]);
}
while(1){
pair <int, int> temp = pq.top();
pq.pop();
tempMinRange = temp.first;
int idx = temp.second;
if(tempMaxRange - tempMinRange < rangeSize){
rangeSize = tempMaxRange - tempMinRange;
minRange = tempMinRange;
maxRange = tempMaxRange;
}
pointers[idx]++;
if(pointers[idx] == nums[idx].size())break;
else{
tempMaxRange = max(tempMaxRange,
nums[idx][pointers[idx]]);
pq.push({nums[idx][pointers[idx]], idx});
}
}
vector <int> ans(2);
ans[0] = minRange;
ans[1] = maxRange;
return ans;
}
};
main(){
Solution ob;
vector<vector<int>> v =
{{4,10,15,25,26},{0,9,14,20},{5,18,24,30}};
print_vector(ob.smallestRange(v));
}입력
{{4,10,15,25,26},{0,9,14,20},{5,18,24,30}};출력
[14, 18]