BOJ 2751 - 수 정렬하기 2

문제 링크

문제#

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력#

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

출력#

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

풀이#

수의 개수가 많아서 단순한 $O(N^2)$ 정렬로는 버티기 어렵다. 주어진 수들이 중복되지 않으므로, 균형 이진 탐색 트리 기반의 set에 넣으면 삽입 과정에서 자동으로 오름차순 정렬 상태가 유지된다.

코드는 모든 수를 set<int>에 삽입한 뒤 순회하며 출력한다. 핵심은 입력 크기에 맞게 $O(N \log N)$ 범위의 정렬 방법을 쓰는 것이고, set 순회 결과가 곧 정렬된 출력이라는 점을 이용한다.

코드#

#include <iostream>
#include <set>
using namespace std;
 
int main() {
 
	set<int> set;
 
	int N;
	cin >> N;
 
	int a;
	for (int i = 0; i < N; i++) {
		cin >> a;
		set.insert(a);
	}
 
	for (int j : set)
		cout << j << '\n';
 
	return 0;
}

복잡도#

• 시간 복잡도: set에 $N$개의 수를 삽입하므로 $O(N \log N)$이다.
• 공간 복잡도: set에 입력 수를 저장하므로 $O(N)$이다.

마무리#

대량의 수를 정렬해야 하므로 $O(N \log N)$ 안에 들어오는 방법을 골라야 한다. 중복이 없는 입력에서는 set에 넣고 순회하는 방식도 정렬 출력으로 이어진다.