문제 개요
여러 개의 리스트가 주어졌을 때, 각 리스트에서 하나의 값을 선택한 뒤 그 값들 중 최댓값과 최솟값의 차이를 계산합니다. 이렇게 만들 수 있는 차이 중 가장 작은 값을 찾는 것이 이 문제의 목표입니다.
예를 들어 입력이 다음과 같다고 가정해 보겠습니다.
lists = [[30, 50, 90], [85], [35, 70]]
첫 번째 리스트에서 90, 두 번째 리스트에서 85, 세 번째 리스트에서 70을 선택하면 최댓값 90과 최솟값 70의 차이는 20이 됩니다. 따라서 출력은 20입니다.
해결 접근 방법
이 문제는 우선순위 큐(priority queue)를 활용하면 효율적으로 해결할 수 있습니다. 각 리스트에서 현재 가리키고 있는 값을 큐에 넣고, 항상 최솟값을 기준으로 차이를 갱신해 나가는 방식입니다.
알고리즘 단계
- maxVal := -inf (현재까지의 최댓값)
- ret := inf (결과로 반환할 최소 차이)
- 우선순위 큐 pq를 정의합니다.
- n := 리스트의 개수
- i := 0부터 n 미만까지 반복하며 다음을 수행합니다.
- lists[i] 배열을 오름차순으로 정렬합니다.
- {lists[i][0], i, 0}을 pq에 삽입합니다. (값, 리스트 인덱스, 위치 인덱스)
- maxVal을 lists[i][0]과 비교해 더 큰 값으로 갱신합니다.
- pq의 크기가 n과 같은 동안 다음을 반복합니다.
- pq의 최상단 원소를 temp에 저장한 뒤 제거합니다.
- ret을 min(ret, maxVal - temp[0])으로 갱신합니다.
- temp의 마지막 원소(위치 인덱스)를 1 증가시킵니다.
- 증가한 위치가 해당 리스트의 크기보다 작다면:
- maxVal을 새로운 값과 비교해 갱신합니다.
- temp[0]을 새로운 값으로 설정합니다.
- temp를 pq에 다시 삽입합니다.
- 최종적으로 ret을 반환합니다.
C++ 구현 예제
아래 코드를 통해 실제 구현을 확인해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
struct Cmp {
bool operator()(vector<int>& a, vector<int>& b) {
return !(a[0] < b[0]);
}
};
class Solution {
public:
int solve(vector<vector<int>>& lists) {
int maxVal = INT_MIN;
int ret = INT_MAX;
priority_queue<vector<int>, vector<vector<int>>, Cmp> pq;
int n = lists.size();
for (int i = 0; i < n; i++) {
sort(lists[i].begin(), lists[i].end());
pq.push({lists[i][0], i, 0});
maxVal = max(lists[i][0], maxVal);
}
while (pq.size() == n) {
vector<int> temp = pq.top();
pq.pop();
ret = min(ret, maxVal - temp[0]);
temp.back()++;
if (temp.back() < lists[temp[1]].size()) {
maxVal = max(maxVal, lists[temp[1]][temp.back()]);
temp[0] = lists[temp[1]][temp.back()];
pq.push(temp);
}
}
return ret;
}
};
int solve(vector<vector<int>>& lists) {
return (new Solution())->solve(lists);
}
int main(){
vector<vector<int>> v = {{30, 50, 90},{85},{35, 70}};
cout << solve(v);
}입력
{{30, 50, 90},{85},{35, 70}}출력
20
동작 원리 정리
이 알고리즘의 핵심은 각 리스트를 정렬된 상태로 유지하면서, 우선순위 큐를 통해 현재 선택된 값들 중 최솟값을 효율적으로 추적하는 것입니다. 최솟값에 해당하는 리스트의 포인터를 한 칸 앞으로 이동시키며 새로운 조합을 탐색하고, 매 단계마다 최댓값과의 차이를 계산해 결과를 갱신합니다.
만약 어떤 리스트의 모든 원소를 소진하면 해당 리스트에서 더 이상 값을 선택할 수 없으므로, 큐의 크기가 n 미만이 되는 순간 반복이 종료됩니다. 이 시점까지 계산된 ret이 바로 우리가 찾는 최소 차이입니다.