[2750,2751번] 수 정렬하기

2750번: 수 정렬하기

 

www.acmicpc.net

2751번: 수 정렬하기 2

 

www.acmicpc.net

/*2750번 수 정렬하기*/
#include <iostream>
#include <algorithm>
using namespace std;
int N;
int arr[1000];

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> arr[i];
	}
	sort(arr, arr + N);//STL사용

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

/*2751번 수 정렬하기*/
#include <iostream>
#include <algorithm>
using namespace std;
int N;
int arr[1000000];

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> arr[i];
	}
	sort(arr, arr + N);//STL사용

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

이 두 정렬 문제는 STL을 이용하면 간단히 풀수 있다.

STL을 사용하지 않고 직접 구현을 한다면 2750번은 N의 범위가 1000이하이기 때문에 

시간복잡도가 O(N^2)인 버블, 삽입 등의 정렬로 풀어도 되지만

2571번은 N의 범위가 1,000,000이기 때문에 시간복잡도가 O(N*logN)인 퀵 정렬, 병합정렬을 이용해 풀면된다.

주의점은 퀵 정렬은 최악의 경우 시간복잡도가 O(N^2)이 될수 있으니 주의 한다.