[백준] 11931번 수 정렬하기 4

문제: 11931번: 수 정렬하기 4

basic-algo-lecture/workbook/0x0E.md at master · encrypted-def/basic-algo-lecture

basic-algo-lecture/workbook/0x0E.md at master · encrypted-def/basic-algo-lecture

 

#include <queue>
#include <iostream>

using namespace std;

int n;
int arr[1000001];
int tmp[1000001]; // merge 함수에서 리스트 2개를 합친 결과를 임시로 저장하고 있을 변수

void merge(int st, int en, int mid) {
	int left = st;
	int right = mid;

	for (int i = st; i < en; i++) {
		if (left == mid) {
			tmp[i] = arr[right++];
		}
		else if (right == en) {
			tmp[i] = arr[left++];
		}
		else if (arr[left] > arr[right]) {
			tmp[i] = arr[left++];
		}
		else {
			tmp[i] = arr[right++];
		}
	}

	// 반영
	for (int i = st; i < en; i++) {
		arr[i] = tmp[i];
	}
}

void merge_sort(int st, int en) {
	// 더이상 쪼갤 수 없는 경우 빠져나가기
	if (st + 1 == en) return;

	int mid = (st + en) / 2;
	merge_sort(st, mid); // 쪼개
	merge_sort(mid, en); // 쪼개
	merge(st, en, mid); // 합쳐
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> arr[i];

	merge_sort(0, n);
	for (int i = 0; i < n; i++)
		cout << arr[i] << "\n";


	return 0;
}

 

이 문제도 머지소트 이용해서 풀었다.

 

 

 

참고자료:

[바킹독의 실전 알고리즘] 0x0F강 - 정렬 II