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

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

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 = (st + en) / 2;
	int lidx = st; // arr[st:mid] 에서 값을 보기 위해 사용하는 index
	int ridx = mid; // arr[mid:en] 에서 값을 보기 위해 사용하는 index
	for (int i = st; i < en; i++) {
		if (ridx == en) tmp[i] = arr[lidx++];
		else if (lidx == st) tmp[i] = arr[ridx++];
		else if (arr[lidx] <= arr[ridx]) tmp[i] = arr[lidx++];
		else tmp[i] = arr[ridx++];
	}

	// 임시로 저장한 정렬된 값을 arr 로 옮기기
	for (int i = st; i < en; i++)
		arr[i] = tmp[i];
}

void merge_sort(int st, int en) {
	if (en == st + 1) return; // 리스트의 길이가 1인 경우
	int mid = (st + en) / 2;
	merge_sort(st, mid); // 나누기
	merge_sort(mid, en); // 나누기
	merge(st, en); // 합치기
}


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] << " ";


	return 0;
}

 

머지 소트 코드 짤 때마다 느끼는 거지만 경계 부분 설정하는게 생각보다 어렵다. 잘못 생각하면 바로 에러떠서..;; 

 

큰 틀 자체는 쉽게 이해할 수 있는데 직접 구현하라고 했을 때 위처럼 st, en 의 범위를 설정하는게 개인적으로 쉽지 않은 것 같다;; ㅠ_ㅠ

 

 

 

참고자료:

[바킹독의 실전 알고리즘] 0x0E강 - 정렬 I - YouTube