(c++)백준 2751번: 수 정렬하기 2

https://www.acmicpc.net/problem/2751

2751번: 수 정렬하기 2

C++ STL의 sort()함수를 쓰면 쉽게 풀 수 있다. 다만 출력할 때 개행을 위해 endl을 쓰면 시간 초과가 나므로 '\n'을 써야 한다.

 

#include <iostream>
#include <algorithm>//sort
#include <vector>
using namespace std;

int N;
vector<int>Num;

void solution() {
	int n;
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> n;
		Num.push_back(n);
	}
	sort(Num.begin(), Num.end());
	for (int i = 0; i < N; i++) {
		cout << Num[i] << '\n';
	}
}

int main() {
	solution();
	return 0;
}

 

quickSort는 보통 O(nlogn)의 시간복잡도가 걸리지만, 최악의 경우 O(n^2)의 시간복잡도가 걸리므로 시간초과가 난다.

 

항상 시간복잡도가 O(nlogn)인 mergeSort를 구현해 보았다.

 

#include <iostream>
#include <vector>
using namespace std;

int N;
vector<int>Num;

void input() {
	int n;
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> n;
		Num.push_back(n);
	}
}

void merge(int start, int mid, int end) {
	vector<int>tmp;//정렬된 함수 저장
	int s1 = start, s2 = mid + 1;//두 분리된 배열의 첫번째 인덱스

	//s1가 mid에 도착하거나, s2가 end에 도착하면 비교 종료
	while (s1 <= mid && s2 <= end) {
		if (Num[s1] > Num[s2]) {
			tmp.push_back(Num[s2]);
			s2++;
		}
		else {
			tmp.push_back(Num[s1]);
			s1++;
		}
	}

	//남은 배열 tmp뒤에 이어붙이기
	while (s1 <= mid) {
		tmp.push_back(Num[s1]);
		s1++;
	}
	while (s2 <= end) {
		tmp.push_back(Num[s2]);
		s2++;
	}

	//tmp를 Num에 넣기
	for (int i = start; i <= end; i++) {
		Num[i] = tmp[i - start];
	}
}

void mergeSort(int start, int end) {
	if (start < end) {
		int mid = start + (end - start) / 2;
		mergeSort(start, mid);
		mergeSort(mid + 1, end);
		merge(start, mid, end);
	}
}

int main() {
	input();
	mergeSort(0, N-1);
	for (int i = 0; i < N; i++) {
		cout << Num[i] << '\n';
	}
	return 0;
}

mergeSort는 C++ STL의 sort함수를 쓰는 방법보다 메모리를 많이 쓰고 시간 또한 오래걸리는 것을 알 수 있었다.