백준 2751번 - 수 정렬하기 2 (C++ / 병합정렬)

 

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

2751번: 수 정렬하기 2

 

한 2~3년? 정도만에 백준을 푸는 것 같다.

일단 간단한 정렬을 이용해서 몸 좀 풀려했다. (이땐 삽질 시작인줄 몰랐다)

문제는 다음과 같다.

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.
입력첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

 

접근법

아무래도 1,000,000 개의 데이터가 주어지기 때문에 시간복잡도가 O(n^2)인 알고리즘 (버블, 선택, 삽입)을 쓰게 되면 비교 횟수가 약 1조 번 가까이 될 것 같아서

힙정렬, 병합정렬, C++ <algorithm>에서 제공해 주는 sort함수

위 3가지 중 한 가지를 사용하려 했다.

 

힙정렬은 priority_queue로 하면 사실 구현할 것도 없으니 연습단계에선 사용하지 않기로 했고,

sort함수도 마찬가지로 일단 패스했다.

 

그럼 남은 것은 병합 정렬하나 인데... 구현을 마치고 난 후 계속 시간초과가 뜨기 시작했다.

처음엔 구현에 문제가 있는 줄 알고 동적배열을 일반배열로도 바꾸어보고, index+=1을 후위연산자로 바꿔보는 등 별의별 방법을 써보았다. 그래도 해결될 기미가 보이지 않자 일단 <algorithm>에서 제공해 주는 sort함수를 쓰기로 사용했는데...

계속 시간초과가 떴다.. 

 

사실 여기서 조금 이상함을 느꼈다. 구현한 병합정렬은 실수로 인해 최적으로 짜지 못해서 시간초과가 날 수 있겠다 싶었지만, algorithm sort함수는 그러지 않을 거란 확신이 있었다.

적어도 sort함수는, O(nlogn)을 보장한다는 것을 알고 있기 때문이다.

조금 구글링을 해본 결과...

 

cout << numList[i] << endl  → cout << numList[i] << "\n";

로 바꿔주니 바로 해결되더라 .. ㅜ_ㅜ 

사실 예전에 백준 풀때도 cin, cout, endl 을 그대로 쓰면 시간 측면에서 불리하다는 것을 까먹고 있었다...

다시 생각났으니 앞으로 문제풀때 조심해야겠다..

 

아무튼! 병합정렬 할 때는 항상 재귀함수 쓰는 부분이 햇갈리는거 같다. 그 부분만 잘 떠올리면 정말 간단하게 짤 수 있다!

 

코드 

 

일단 아래처럼 코드를 구성했다.

①병합정렬로 짜보기

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


vector<int> numList;

// [][] | [][] | [][] | [][]

void Merge(int left, int right)
{
	int mid = (left + right) / 2;
	int leftIdx = left;
	int rightIdx = mid + 1;
	vector<int> result;
	while (leftIdx <= mid && rightIdx <= right)
	{
		if (numList[leftIdx] < numList[rightIdx])
		{
			result.push_back(numList[leftIdx]);
			leftIdx++;
		}
		else
		{
			result.push_back(numList[rightIdx]);
			rightIdx++;
		}
	}

	if (rightIdx >= left)
	{
		for (int i = leftIdx; i <= mid; i++)
		{
			result.push_back(numList[i]);
		}
	}
	else
	{
		for (int i = rightIdx; i <= right; i++)
		{
			result.push_back(numList[i]);
		}
	}

	for (int i = 0; i < result.size(); i++)
	{
		numList[left + i] = result[i];
	}
}

void MergeSort(int left, int right)
{
	if (left >= right)
		return;
	int mid = (left + right) / 2;
	MergeSort(left, mid);
	MergeSort(mid + 1, right);

	Merge(left, right);


}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int N;
	cin >> N;
	const int i = N;
	for (int i = 0; i < N; i++)
	{
		int num;
		cin >> num;
		numList.push_back(num);
	}

	MergeSort(0, N-1);
	for (int i = 0; i < N; i++)
	{
		cout << numList[i] << "\n";
	}
	return 0;
}

 

② algorithm sort함수를 이용해 풀기

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

vector<int> numList;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int N;
	cin >> N;
    int num;
	for (int i = 0; i < N; i++)
	{

		cin >> num;
		numList.push_back(num);
	}
	sort(numList.begin(), numList.end());
	for (int i = 0; i < N; i++)
	{
		cout << numList[i] << "\n";
	}

	return 0;
}

삽질의 흔적... ;-;