[BOJ/C++] 수 정렬하기 3(10989번)

1. 개요

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

10989번: 수 정렬하기 3

1-1. 설명

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

1-2. 제한 사항

 - 첫 줄에 수의 개수 N이 주어짐

 - N은 1 이상 10,000,000이하 자연수

 - 둘째 줄부터 수가 주어지며 10,000보다 작거나 같은 자연수

---

2. 구현

2-1. 풀이

단순히 입력받아서 sort하면 메모리 초과가 일어난다. 메모리는 8MB이며, 수는 10,000,000개가 들어오므로 10MB까지 커지기 때문이다. 수를 입력받아서 배열에 저장하는 것이 아닌, 정수를 세는 count 배열을 생성하여 count 개수를 세고 for문으로 1부터 출력하면 된다. 주의할 점은 입출력 연산 속도를 향상시키기 위해 표준 스트림의 동기화를 꺼주어야 한다. 이를 해주지 않으면 시간 초과가 나타난다. 

2-2. 코드

#include <iostream>
using namespace std;

constexpr size_t MAX_NUM = 10001;
int nums[MAX_NUM];

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int count, num;
	cin >> count;
	for (int i = 0; i < count; i++) {
		cin >> num;
		nums[num]++;
	}
	for (int i = 1; i < MAX_NUM; i++) {
		if (nums[i] == 0) continue;
		else {
			for (int j = 0; j < nums[i]; j++) {
				cout << i << "\n";
			}
		}
	}
	return 0;
}