2751번: 수 정렬하기 2

문제:

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력:

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

풀이:

어떤 종류의 정렬을 이용해야 될까 고민 하다가 병합 정렬(Merge Sort)이나 C++ STL에 sort() 함수를 이용할까 고민하다가 간단한 sort() 함수를 먼저 이용해보고 시간 초과로 안풀리면 병합 정렬을 이용할려고 하였다. 최악의 경우에 sort() 함수는 시간 복잡도가 O(N^2)이기 때문이였다.

코드:

#include <iostream>
#include <algorithm>

using namespace std;

int main(void){
	int n;
	cin >> n;
	
	int numbers[n];
	
	for(int i = 0; i < n; i++){
		cin >> numbers[i];
	}
	sort(numbers, numbers+n);
	for(int i = 0; i < n; i++){
		cout << numbers[i] << '\\n'; // '\\n' 안쓰면 시관 초과
	}
}

핵심 포인트:

이 문제의 핵심 포인트는 답을 출력시 'endl'을 이용하는 것이 아닌 '\n'을 활용하여 문제를 풀어야 한다. 만약에 'endl'을 이용하게 되면 시간 초과로 오답 처리가 된다. 아마 'endl'은 std 라이브러리를 한번 거쳐서 출력을 하는 것이라서 시간을 더 사용하는 것인 것 같다. 백준 게시판에서 찾아보니 알고리즘 문제 풀이 할 때는 줄 바꿈을 'endl'이 아닌 '\n'을 이용하는게 좋다고 한다.

병합정렬 풀이:

코드1:

메모리를 아낄려고 글로벌 변수를 안만들고 계속 sorted[]를 계속 passing하는 식으로 하였지만 메모리에서 큰 차이가 없었음 고로 글로벌 변수를 선언하는 방식이 조금 더 깔끔한 듯

#include <iostream>

using namespace std;

int* merge(int numbers[], int start, int middle, int end, int sorted[]){
	int i = start;
	int j = middle + 1;
	int k = start;
	 
	while(i <= middle && j <= end){
		//i와 j중 더 큰 것을 sorted[]에 순서대로 비교하면서 넣음 
		if(numbers[i] <= numbers[j]){
			sorted[k] = numbers[i];
			i++;
		} else{
			sorted[k] = numbers[j];
			j++;
		}
		k++;
	}

	//분할 된 한쪽이 먼저 넣어질 경우 남은 한쪽 데이터 다 넣음 
	if(i > middle){
		for(int temp = j; temp <= end; temp++){
			sorted[k] = numbers[temp];
			k++;
		}
	} else{
		for(int temp = i; temp <= middle; temp++){
			sorted[k] = numbers[temp];
			k++;
		}
	}

	//정렬 된 배열 삽입
	for(int temp = start; temp <= end; temp++){
		numbers[temp] = sorted[temp];
	}
	return numbers;
}

int* mergeSort(int numbers[], int start, int end, int sorted[]){
	if(start < end){
		int middle = (start + end)/2;
		mergeSort(numbers, start, middle, sorted);
		mergeSort(numbers, middle+1, end, sorted);
		merge(numbers, start, middle, end, sorted);
	}
	return numbers;
}

int main(void){
	int n;
	cin >> n;
	
	int numbers[n];
	int sorted[n];
	int *random;
	
	for(int i = 0; i < n; i++){
		cin >> numbers[i];
	}
	
	//random = mergeSort(numbers, 0, n, sorted);
	random = mergeSort(numbers, 0, n-1, sorted);
	
	for(int i = 0; i < n; i++){
		cout << random[i] << '\\n';
	}
}

코드 2: