23.03.01. 풀었던 문제들

Leetcode 912. Sort an Array

 문제는 STL 없이 O(nlogn)의 정렬 함수를 만드는 것이다. - 대표적으로 구현하기 쉬운 merge sort를 쓰면 된다.

class Solution {
public:
    vector<int> arr;
    void merge(int start, int end){
        if(start == end) return;

        int mid = (start + end) / 2;
        // left : mid 포함, right: mid 포함 x
        vector<int> left(arr.begin() + start, arr.begin() + mid + 1), right(arr.begin() + mid + 1, arr.begin() + end + 1);
        int leftlen = left.size(), rightlen = right.size();

        int leftidx = 0, rightidx = 0, arridx = start;
        while(leftidx < leftlen && rightidx < rightlen){
            if(left[leftidx] < right[rightidx]){
                arr[arridx] = left[leftidx];
                arridx++; leftidx++;
            }
            else{ // left[leftidx] >= right[rightidx]
                arr[arridx] = right[rightidx];
                arridx++; rightidx++;
            }
        }

        while(leftidx < leftlen){
            arr[arridx] = left[leftidx];
            arridx++; leftidx++;
        }
        while(rightidx < rightlen){
            arr[arridx] = right[rightidx];
            arridx++; rightidx++;
        }
    }
    void merge_sort(int start, int end){
        if(start >= end) return;
        int mid = (start + end) / 2;
        merge_sort(start, mid);
        merge_sort(mid + 1, end);
        merge(start, end);
    }
    vector<int> sortArray(vector<int>& nums) {
        arr = nums;
        merge_sort(0, nums.size()-1);
        return arr;
    }
};

 

 문제 조건에서, '가능 한 한 적은 메모리를 사용'하라는 조건이 붙었기 때문에, O(nlogn)의 시간복잡도, O(n)의 공간복잡도를 사용하는 merge sort 대신 O(1)의 공간복잡도 (추가적인 공간을 사용하지 않음), O(nlogn)의 시간복잡도를 가지는 heap sort가 적절할 것이다.