백준 2751 c++ "수 정렬하기 2" -PlusUltraCode-

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

 

[필자 사고]

정렬 문제이다.

이 문제의 핵심은 N의 갯수가 1~ 1000000 이라는 점이다.

버블정렬과 같은 시간복잡도가 N^2인 경우를 사용할경우 1억번의 연산을 초과하여 시간초과가 발생한다.

그렇다면 N^2이 아닌 NlongN 정렬 알고리즘을 사용해야 된다.

 

c++ 대표적인 벡터 내적함수 ;sort를 사용하면 문제를 쉽게 해결할 수 있다.

 

[소스 코드]

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N;
vector<int> arr;
	

void Input() {
	cin >> N;
	arr.resize(N);
	for (int i = 0; i < N; i++) {
		cin >> arr[i];
	}
	sort(arr.begin(), arr.end());

}

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



int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	Input();
	Print();

}