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

1. 문제 링크

www.acmicpc.net/problem/2751

2751번: 수 정렬하기 2

 

 

 

2. 문제 설명

N개의 수를 입력받은 후, 오름차순으로 정렬하여 출력하는 문제입니다.

 

 

 

3. 소스코드

BOJ 2751번 수 정렬하기 2 C++ 풀이입니다.

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

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	int N;
	int arr[1000000];
	cin >> N;
	for (int i = 0; i < N; i++)
		cin >> arr[i];

	sort(arr, arr + N);
	for (int i = 0; i < N; i++)
		cout << arr[i] << '\n';

	return 0;
}

sort함수를 이용한 풀이입니다.

sort함수를 사용하기 위해서는 <algorithm> 헤더 파일을 include 해줘야 합니다.

sort함수의 사용법은 sort(시작 지점, 끝 지점) 입니다.

시작 지점을 포함하고, 끝 지점을 포함하지 않는 범위까지 오름차순으로 정렬을 해줍니다.

 

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

void quick_sort(int *arr, int start, int end)
{
	int pivot = arr[start];
	int left = start + 1;
	int right = end;

	if (start >= end)
		return;
	while (true) {
		while (left <= right && arr[left] <= pivot)
			left++;
		while (left <= right && arr[right] >= pivot)
			right--;
		if (left > right)
			break;
		swap(arr[left], arr[right]);
	}
	swap(arr[start], arr[right]);
	quick_sort(arr, start, right - 1);
	quick_sort(arr, right + 1, end);
}

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	int N;
	int arr[1000000];
	cin >> N;
	for (int i = 0; i < N; i++)
		cin >> arr[i];

	random_shuffle(arr, arr + N);
	quick_sort(arr, 0, N - 1);
	for (int i = 0; i < N; i++)
		cout << arr[i] << '\n';

	return 0;
}

 

퀵 정렬을 이용한 풀이입니다.

퀵 정렬의 시간 복잡도는 평균적으로 O(nlogn)이지만, 최악의 경우 O(n^2)입니다.

이 문제의 경우 O(nlogn)으로만 풀 수 있기 때문에 38번 라인을 주석 처리하면 시간 초과가 납니다.

퀵 정렬의 최악의 경우는 순서대로 정렬되어있거나, 거꾸로 정렬되어 있는 경우이므로

38번 라인에서 random_shuffle(arr, arr + N); 을 사용하여 랜덤으로 섞어서 이러한 경우를 방지했습니다.

STL의 sort함수의 경우 퀵 정렬, 힙 정렬, 삽입 정렬을 혼합해서 사용하는 인트로 정렬로 구현되어 있어 최악의 경우에도 O(nlogn) 입니다.