[백준] 10989번: 수 정렬하기 3 [C++]

 

알고리즘 분류: 정렬

문제 링크: https://www.acmicpc.net/problem/10989

10989번: 수 정렬하기 3

 

【 문제 】

 

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

 

 

【 입력 】

 

첫째 줄에 수의 개수 N(1 <= N <= 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.

 

 

【 출력 】

 

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

 

 

 

【 풀이 】

 

시간 복잡도, 공간 복잡도 모두 신경 써야 하는 문제이다.

수의 개수는 10,000,000개로 굉장히 많다. 문제의 메모리 제한은 8MB로, vector를 이용하여도 메모리 초과가 나온다.

또한 sort()를 포함한 기존에 사용하던 정렬 알고리즘으로는 시간 초과가 발생한다.

따라서 이 문제에서는 계수 정렬(Counting Sort) 알고리즘을 사용해야 한다.

계수 정렬이란 각 숫자의 등장 횟수를 세는 알고리즘이다. 즉 수의 범위를 활용하는 알고리즘인 것이다.

문제에서 수의 범위는 10,000이 최대이므로 10,000의 크기를 가진 배열은 0.03MB의 메모리를 차지하게 되어 메모리 초과는 피할 수 있다.

그러나 계수 정렬을 사용해도 시간 초과가 나오게 되는데, 이는 시간 복잡도와는 별개로 입출력이 실행 속도에서 차지하는 비중이 꽤 크기 때문이다. 따라서 메인 함수 최상단에

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

 

 

위 문구를 추가해 주어 빠른 입출력을 유도하는 것이 좋다.

위 문구를 추가한다는 것은 C 표준 스트림 버퍼와의 동기화를 끊는다는 것이다.

이에 따라 C++ 만의 독립적인 버퍼를 갖게 되고, 거의 모든 언어 입출력 속도에서 최상위권에 위치하게 된다.

 

 

 

【 코드 】

 

#include<iostream>
using namespace std;

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int cnt[10001] = { 0 };
	int n,count;
	cin >> n;

	for (int i = 0; i < n; i++)
	{
		cin >> count;
		cnt[count]++;
	}

	for (int i = 1; i < 10001; i++)
		for (int j = 0; j < cnt[i]; j++)
			cout << i<<'\n';

	return 0;
}