[LeetCode] 632. Smallest Range Covering Elements from K Lists

https://leetcode.com/problems/smallest-range-covering-elements-from-k-lists/description/?envType=daily-question&envId=2024-10-13

leetcode - Smallest Range Covering Elements from K Lists

문제 유형: 정렬, 슬라이딩 윈도우

문제 난이도: Hard

 

문제

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

We define the range [a, b] is smaller than range [c, d] if b - a < d - c or a < c if b - a == d - c.

 

비내림차순으로 정렬된 k개의 리스트가 있다.

각 k개의 리스트의 요소를 적어도 하나씩 가지는 가장 작은 범위를 구하시오.

b-a < d-c 또는 b-a = d-c이면서 a < c인경우, [a, b]가 [c, d]보다 작은 범위라고 합니다.

 

풀이

우선, 배열에 {수, 리스트 고유번호}의 형태로 저장시키고, 정렬한다. 이를 arr이라 부르겠다.

그러면 모든 요소들이 정렬되고, 각각의 수의 소속성(membership)을 알 수 있다.

두 인덱스 포인터 left와 right, 두 범위를 나타낼 숫자 rangeStart, rangeEnd, 범위 내 요소들의 중복없는 그룹수를 저장할 uniqueLists를 변수로 만들고, count[그룹번호] = 현재 범위내에서의 그 그룹의 요소개수형태로 저장할 해시맵 count를 만든다.

추가로, 수의 범위 폭을 저장할 minWidth를 INT_MAX로 초기화한다.

 

right를 한 칸씩 밀며, 다음을 진행한다:

  범위에 arr[right].first를 추가할 것이다.

  count[arr[right].second]가 0이면, 현재 arr[right].second번의 그룹 요소가 없었다는 의미이므로, uniqueLists를 1 추가한다.

  count[arr[right].second]를 1 추가한다.

 

  만약 uniqueLists가 n이면, 최소한 그룹별로 하나씩의 요소가 들어있다는 뜻이므로, 범위를 좁혀보자. left를 최대 right까지 밀어보자.

    우선 그 전에, 범위 업데이트부터 한다.

    만약 기존 최소범위보다 현재 범위가 더 작다면, 범위 관련 값들을 업데이트한다. 그 후, 범위에서 제거할 것이다.

     count[arr[left].second]를 1 빼주고, 0이 되었다면 uniqueLists를 1 내린다. 이게 무슨 뜻인지는 이제 알 것이다.

    이제 left를 1칸 밀면 된다.

 

최종적으로 남은 {rangeStart, rangeEnd}를 반환하면 된다.

 

 

코드

C++

#pragma GCC optimize("03", "unroll-loops");
static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

class Solution {
public:
    vector<int> smallestRange(vector<vector<int>>& nums) {
        vector<pair<int, int>> arr;
        int n = nums.size();
        for(int i = 0; i < n; ++i) {
            for(const auto &x : nums[i]) {
                arr.push_back({x, i});
            }
        }

        sort(arr.begin(), arr.end());
        unordered_map<int, int> count;
        int left = 0, minWidth = INT_MAX;
        int rangeStart = -1, rangeEnd = -1;
        int uniqueLists = 0;

        for(int right = 0; right < arr.size(); ++right) {
            int rightVal = arr[right].first;
            int listIdx = arr[right].second;

            if(count[listIdx] == 0) {
                uniqueLists++;
            }
            count[listIdx]++;

            while(uniqueLists == n && left <= right) {
                int leftVal = arr[left].first;
                int currRange = rightVal - leftVal;

                if(currRange < minWidth) {
                    minWidth = currRange;
                    rangeStart = leftVal;
                    rangeEnd = rightVal;
                }

                int leftListIdx = arr[left].second;
                count[leftListIdx]--;
                if(count[leftListIdx] == 0) {
                    uniqueLists--;
                }
                left++;
            }
        }

        return {rangeStart, rangeEnd};
    }
};