Leetcode - 315. Count of Smaller Numbers After Self 풀이 [H]

문제

주어진 배열에서 자기 자신의 오른쪽에 있는 값들중 자신보다 작은 값의 갯수를 구하라.

Input: nums = [5,2,6,1]
Output: [2,1,1,0]
Explanation:
To the right of 5 there are 2 smaller elements (2 and 1).
To the right of 2 there is only 1 smaller element (1).
To the right of 6 there is 1 smaller element (1).
To the right of 1 there is 0 smaller element.

해결 아이디어 merge sort

• nums[l] > nums[r] 일 때는 그 횟수를 cnt를 누적해서 더하다가.
  크기가 반대가 되는 순간 (그동안 누적해서 더한 값이 [l] 의 오른쪽에있는 작은값의 갯수다)
  cnt값은 현재까지의 nums[l] 값의 오른쪽 작은수의 갯수다.
  l 은 지금까지 r보다 큰값의 갯수를 더할 수 있게 된다.
  7 6 1 2

• 이해하기 어렵지만 굉장히 좋은 문제라고 생각. 머지소트의 동작방식과 성질 그리고 응용할수 있는 것에 대한 이해를 높히는데 좋은 문제다.

해결

주석을 참고할것.

class Solution {
public:
    vector<int> result;
    void merge_count(vector<pair<int, int>> &nums, int left, int mid, int right) {
        vector<pair<int, int>> sorted(right - left + 1, make_pair(0,0));
        int l = left;
        int r = mid + 1;
        int i = 0;
        int cnt = 0;
        while (l <= mid && r <= right) {
            if (nums[l].first > nums[r].first) {
                cnt++; // count if left is greater
                sorted[i++] = nums[r++];
            } else {
                // right is greater
                // at this point [l] is previous greater one, so can be added accumulated cnt value at nums[l].
                result[nums[l].second] += cnt; // save the cnt value at original index
                sorted[i++] = nums[l++];
            }
        }
        while (l <= mid) {
            result[nums[l].second] += cnt; // left is always greater than right in this point.
            sorted[i++] = nums[l++];
        }
        while (r <= right) {
            sorted[i++] = nums[r++];
        }
        for (auto it: sorted)
            nums[left++] = it;
    }
    void merge_sort(vector<pair<int, int>> &nums, int left, int right) {
        if (left >= right)
            return;
        int mid = left + (right - left) / 2;
        merge_sort(nums, left, mid);
        merge_sort(nums, mid + 1, right);
        merge_count(nums, left, mid, right);
    }
    vector<int> countSmaller(vector<int>& nums) {
        // make new nums array which contain (value, index)
        vector<pair<int, int>> newnum(nums.size(), make_pair(0,0));
        result = vector<int>(nums.size(), 0);
        for (int i = 0; i < nums.size(); i++) {
            newnum[i] = make_pair(nums[i], i);
        }
        // sort newnum array
        merge_sort(newnum, 0, nums.size()-1);
        return result;
    }
};