[백준 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);
}