[C++] Interview Question : find smallest range

| Question 

You have k lists of sorted integers. Find the smallest range that includes at least one number from each of the k lists.

For example,
List 1: [4, 10, 15, 24, 26]
List 2: [0, 9, 12, 20]
List 3: [5, 18, 22, 30]

The smallest range here would be [20, 24] as it contains 24 from list 1, 20 from list 2, and 22 from list 3.

 

번역 : 

정수로 이루어진 배열 k개가 주어졌을 때, 각 배열의 원소를 적어도 하나 포함하는 가장 작은 범위를 찾아라. 

예를 들어, 아래와 같은 배열 3 개가 주어졌을 때

List 1: [4, 10, 15, 24, 26]
List 2: [0, 9, 12, 20]
List 3: [5, 18, 22, 30]

range [20, 24]는 list 1에서 24를, list 2에서 20을 list 3에서 22를 포함하는 가장 작은 범위이다. 

---

| Solution

문제를 풀 때 고려한 사항

• List라고 주어졌지만, 주어지는 input이 배열이라고 가정한다.
• 임의의 배열의 원소가 한 개도 없거나, 혹은 정답인 range 가 없는 경우는 없다고 가정한다. 그렇다면 문제 자체가 성립하지 않기 때문이다.
• 배열에 나타나는 정수들의 범위는 integer의 범위라고 가정한다.
• 각 배열의 크기는 다를 수 있다.
• 각 배열의 원소는 정렬된 상태로 주어진다. 이는 매우 중요한 정보이다.

Method1

가장 작은 범위를 [strat, end]라고 가정했을 때, end - start 값이 가장 작은 값이 되는 범위를 찾으면 되는 문제이다. 
당연히 start == end 일 때 가장 작은 범위이고, start > end 인 경우는 없다. 

예로 주어진 List를 손으로 풀어보자. 

0~30 기준으로 각 리스트의 원소를 제외한 그림

일부 List의 원소 한개를 기준으로 범위를 넓혀가며 다른 모든 리스트가 포함되는지 찾아보면 될 것 같다. 

그렇다면 여기서 시간을 최소로 할 수 있는 방법은 원소의 개수가 가장 적은 List를 기준으로, 각 원소에 대해 범위를 넓혀가며 찾는 방법이 있다.  어쨌건 모든 List의 원소 한 개는 포함되어야 하기 때문이다. 

선택된 List의 원소 개수를 n이라 하고, 모든 List의 수를 k라 한다면 시간복잡도는 

O(nk) * O(범위를 0부터 하나씩 넓혀가는 로직) * O(k(가장 적은 리스트를 찾는 과정))

이 될 것이다. 굉장히 시간 복잡도가 높아 보인다. 

Method2

생각해본다면 Sol1에서 범위를 하나씩 넓혀가는 것은 너무 오래 걸리고 의미가 없다.  가장 작은 범위이기 때문에 각 아이템이 범위의 끝이 되면 되지 않을까? 그렇다, k개의 list 중 각 원소가 range의 끝이 돼야만 최소 range를 찾을 수 있다. 

그렇다면, 각 첫번 째 원소를 시작으로 range를 찾아보자 

List 1: [4, 10, 15, 24, 26]
List 2: [0, 9, 12, 20]
List 3: [5, 18, 22, 30]

---

step 1.  [0, 4, 5] -> range 6 // 여기서 최솟값을 빼고 나머지 List의 그다음 원소 중 최솟값을 넣는다. 
step 2. [9, 4, 5] -> range 6
step 3. [9, 10, 5] -> range 6
step 4. [9, 10, 18] -> range 10
step 5. [12, 10, 18] -> range 7
step 6. [12, 15, 18] -> range 7
step 7. [20, 15, 18] -> range 6
step 8. [20, 24, 18] -> range 7
step 9. [20, 24, 22] -> range 5 // min range 한 원소가 끝에 도달했기 때문에 그 리스트를 제외하고 찾는다. 
step 10. [20, 24, 30] -> range 11
step 11. [20, 26, 30] -> range 11 // finish

이런 식으로 찾는다면 따로 가장 원소가 작은 리스트를 찾는 과정도 필요 없다. 따라서 원소가 가장 많은 리스트의 수를 n이라 하면 시간 복잡도 O(nk), 공간복잡도 O(1)에 해결할 수 있다.

그렇다면 코드는 어떻게 구성해야 할까?

만약 리스트가 3개라면 그냥 일반 변수로 3개를 두고 구현하면 될 것 같다. 하지만 리스트의 개수가 그 이상이라면 애매하다. 별도의 자료구조가 필요할 것 같다. 최솟값을 항상 구해야 하기 때문에 그런 시나리오에 유리한 min_heap을 사용하였다. 바로 최솟값을 제거하고 새로운 값을 넣을 수 있다. 

 

구현할 Solution의 Logic을 생각해보자. 

1. 각 list의 첫 번째 원소를 min_heap에 모두 넣는다. 
    1-1. 1의 과정에서 각 list의 원소 중 최댓값을 기억해 놓는다. 
2. min_heap에서 list의 최솟값을 제거한다.  
    2-1. 만약 list의 최솟값을 제거할 때 그다음 원소가 없다면? 해당 리스트는 제외하고 진행해야 할까?
    2-2. 만약 한 list의 마지막 원소까지 도달했고, 그 원소를 제거해야 한다면, 해당 원소가 최솟값이라는 뜻이다.
    2-3. 고로 만약 한 원소가 끝에 도달했고, 해당 원소를 제거해야 할 상황이라면 루프를 종료하면 된다. 
3. 해당 list의 다음 값을 min_heap에 넣는다. 즉, 2에서 해당 list의 정보가 필요하다. 
    3-1. 이때, 최댓값을 갱신해준다. 따로 최댓값을 위한 인덱스 정보는 필요가 없다. 어차피 최솟값만 계속 빠지기 때문이다. 
4. 2~3의 과정을 반복하며 range가 최소라면 갱신해준다. 

 

자 이제 생각한 Logic을 Code로 구현해보자.

 

#include <iostream>
#include <queue>
#include <vector>
#include <climits>

using namespace std;

struct Range {
	int start;
	int end;
};

struct ValListNumIndex{
    int val;
    int list_num;
    int index;
};

struct cmp{
    bool operator()(ValListNumIndex data1, ValListNumIndex data2)
    {
        return data1.val > data2.val;
    }
};

Range FindSmallestRange(vector<vector<int>>& lists) {
	priority_queue<ValListNumIndex, vector<ValListNumIndex>, cmp> min_heap;
	int max = INT_MIN;
	int range_len = INT_MAX;
	Range ans;

	// 1. 각 list의 첫 번째 원소를 min_heap에 모두 넣는다. 
	// 1-1. 1의 과정에서 각 list의 원소 중 최댓값을 기억해 놓는다. 
	for (int idx = 0; idx < lists.size(); idx++) {
		min_heap.push({ lists[idx][0], idx, 0 });
		if (lists[idx][0] > max) max = lists[idx][0];
	}


	// 4. 2~3의 과정을 반복하며 range가 최소라면 갱신해준다. 
	while (true) {
		// 2. min_heap에서 list의 최솟값을 제거한다.  
		ValListNumIndex top = min_heap.top();
		min_heap.pop();

		if (top.index >= lists[top.list_num].size()) break;

		// range 갱신 부분
		if (max - top.val < range_len) {
			range_len = max - top.val;
			ans.start = top.val;
			ans.end = max;
		}
		cout << ans.start << ' ' << ans.end << endl;

		// 3. 해당 list의 다음 값을 min_heap에 넣는다. 
		// 3-1. 최댓값을 갱신해주는데,
		if (lists[top.list_num][top.index + 1] > max) max = lists[top.list_num][top.index + 1];
		min_heap.push({ lists[top.list_num][top.index + 1], top.list_num, top.index + 1 });
	}

	return ans;
}
int main()
{   
    vector<vector<int>> input;
    input.push_back({4, 10, 15, 24, 26});
    input.push_back({0, 9, 12, 20});
    input.push_back({5, 18, 22, 30});

    Range ans = FindSmallestRange(input);

    cout << ans.start << ' ' << ans.end << endl;
    return 0;    
}