(C++) BOJ/백준 2751 - 수 정렬하기 2

문제 출처 : BOJ 2751 - 수 정렬하기 2 www.acmicpc.net/problem/2751

 

 

<algorithm>의 sort() 라는 정렬 함수를 배우게 되어서 정렬 문제를 한번 풀어보았다.

수를 입력 받아서 오름차순으로 정렬하는 문제이다.

C언어에서 기본적으로 사용하던 swap() 함수를 이용한 정렬은 시간복잡도가 O(n^2)이어서 시간 초과가 떴었다.

 

최종 코드

#include <iostream>
#include <algorithm>
using namespace std;
#define MAX 1000000

int arr[MAX];

int main() {
	int n;
	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;
}

arr[]이라는 int형 배열을 만들었다.

최대 크기가 너무 커서 main() 함수 밖에서 선언해주었다.

 

arr[] 배열에 n만큼 문자를 입력받고,

sort()함수를 이용해 안에 있는 원소를 오름차순으로 정렬해주었다. (세번째 parameter를 쓰지 않으면 기본적으로 오름차순으로 정렬된다.)

sort()함수를 이용한 정렬은 시간복잡도가 O(nlogn)이어서 원래 쓰던 정렬의 시간복잡도인 O(n^2)보다 훨씬 빨리 끝낼 수 있다.

오름차순으로 정렬된 arr[] 배열을 처음부터 출력하면 된다.

 

sort() 함수 하나만으로 이렇게 짧게 정렬 문제를 해결할 수 있다니.. 아주 좋은 함수인 것 같다.