[백준] boj 2751

BOJ 2751 정렬문제

1. 풀이 방식 : Merge Sort로 NlogN 타임에 구현

   - 직접 머지 소스 구현

   - stl을 사용한 구현

2. 유의 사항 : C++ 입출력을 사용시 TimeOut이 나옴

 

* Merge 코드 구현

#include <iostream>
#include <stdio.h>
using namespace std;

#define MAX 1000000


int sort[MAX];

// 오름차순 정렬
// st ~ mid, mid + 1 ~ en
void merge(int* list, int start, int mid, int end) {

	int i = start;
	int j = mid + 1;
	int k = start;
	int l;

	while (i <= mid && j <= end) {
		if (list[i] <= list[j]) sort[k++] = list[i++];	
		else sort[k++] = list[j++];
	}

	if (i > mid) for (l = j; l <= end; ++l) sort[k++] = list[l];
	else for (l = i; l <= mid; ++l) sort[k++] = list[l];
	
	for (l = start; l <= end; ++l) list[l] = sort[l];	
}

void mergesort(int* list, int start, int end) {
	int mid;

	if (start < end) {
		mid = (start + end) / 2;
		mergesort(list, start, mid);
		mergesort(list, mid + 1, end); 
		merge(list, start, mid, end);
	}
}

int main() {
	int n;
	scanf("%d", &n);

	int arr[MAX];

	for (int i = 0; i < n; i++)
		scanf("%d", &arr[i]);

	mergesort(arr, 0, n - 1);

	for (int i = 0; i < n; i++)
		printf("%d\n", arr[i]);

	return 0;
}

 

* STL 사용

#include <iostream>
#include <stdio.h>
#include <algorithm>

using namespace std;

#define MAX 1000000

int main() {
	int T;
	int arr[MAX];

	cin >> T;

	for (int i = 0; i < T; ++i)
		cin >> arr[i];
	
	sort(arr, arr + T);

	for (int i = 0; i < T; ++i)
		printf("%d\n", arr[i]);

	return 0;
}