[백준 2751번] 수 정렬하기 2

문제 링크: 2751번 수 정렬하기 2

https://www.acmicpc.net/problem/2751

 

merge sort를 C++로 구현해 보았다.

 

#include <iostream>
#include <vector>
using namespace std;

vector<int> sliceVector(vector<int> arr, int start, int end) {
    // arr[end]는 결과에 포함되지 않는다.
    // 파이썬에서 슬라이싱과 동일하게 구현했다.
    vector<int> res;
    for (int i=start; i<end; i++) {
        res.push_back(arr[i]);
    }
    return res;
}

void printVector(vector<int> arr) {
    for (int i=0; i<arr.size(); i++) {
        cout << arr[i] << '\n';
    }
}

vector<int> merge(vector<int> left, vector<int> right) {
    vector<int> res;

    int i=0, j=0;
    
    while((i<left.size())&&(j<right.size())) {
        if (left[i]<=right[j]) {
            res.push_back(left[i++]);
        } else {
            res.push_back(right[j++]);
        }
    }
    while(i<left.size()) res.push_back(left[i++]);
    while(j<right.size()) res.push_back(right[j++]);

    return res;
}

vector<int> mergeSort(vector<int> arr) {
    // 배열 길이가 0 또는 1이면 그대로 return
    if (arr.size() <= 1) {
        return arr;
    }

    // left와 right로 슬라이스
    vector<int> left = sliceVector(arr, 0, arr.size()/2);
    vector<int> right = sliceVector(arr, arr.size()/2, arr.size());
    // left와 right를 정렬
    left = mergeSort(left);
    right = mergeSort(right);
	// left와 right를 병합
    return merge(left, right);
}

vector<int> init() {
    int n; cin >> n;
    vector<int> arr;
    for (int i=0; i<n; i++) {
        int temp; cin >> temp;
        arr.push_back(temp);
    }
    return arr;
}

int main(void) {
    vector<int> arr = init();
    arr = mergeSort(arr);
    printVector(arr);
}