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

 

 

 

 

 

문제

 

소스코드

 

#include<iostream>
constexpr int  MAX = 1'000'000;
//constexpr int  MAX = 10000;

int tempArray[MAX];

void Merge(int* list, int begin, int mid, int end) {
	int i = begin;
	int j = mid + 1;
	int k = begin;
	for (; k <= end; ++k) {
		if (j > end) tempArray[k] = list[i++];
		else if (i > mid)tempArray[k] = list[j++];
		else if (list[i] < list[j])tempArray[k] = list[i++];
		else tempArray[k] = list[j++];
	}
	for (int t = begin; t <= end; ++t)
		list[t] = tempArray[t];
}

void Split(int* list, int begin, int end) {
	if (begin < end) {
		int middle = (begin + end) / 2;
		Split(list, begin, middle); //계속 나눈다.
		Split(list, middle + 1, end);// 계속 나눈다.
		Merge(list, begin, middle, end);
	}
	else return;
}


int list[MAX];
int main() {
	int max;
	std::cin >> max;
	for (int i = 0; i < max; ++i) {
		std::cin >> list[i];
	}
	Split(list, 0, max - 1);

	for (int i = 0; i < max; ++i)
		std::cout << list[i] << "\n";
}

 

후기

꽤 고생했던 문제이다. 기존 병합 정렬을 구현한 코드에서도 시간 초과가 생겨서 잘못 구현한 거 같아 위키 코드까지 사용해서 해봤지만 계속 시간 초과가 걸려서 고생을 하고 있었는데 마침 아래의 팁을 발견할 수 있었고 5번 문항을 수정하니까 통과하였다.. 기존 코드 또한 문제없이 통과할 수 있었다.

2020/01/10 - [자료구조 알고리즘/심화 정렬 알고리즘] - 병합 정렬(Merge Sort)

endl이 얼마나 느린지도 배울 수 있었고 다음부턴 시간이 필요한 알고리즘에서는 \n을 사용해야겠다. 

 

출처 및 레퍼런스

문제 링크:https://www.acmicpc.net/problem/2751

팁 링크: https://www.acmicpc.net/board/view/31887