백준 10989 - 수 정렬하기 3

문제 번호: 10989

문제 제목: 수 정렬하기 3

문제 주소: https://www.acmicpc.net/problem/10989

문제 내용

최대 1000만개의 숫자를 오름차순으로 출력한다. 입력되는 수는 10000보다 작거나 같은 자연수다.

테스트 케이스

10 5 2 3 1 4 2 3 5 1 7

1 1 2 2 3 3 4 5 5 7

문제 풀이

제목은 정렬하기라고 하지만 처리에는 실제로는 정렬 알고리즘을 사용하지 않는 문제다. 순순히 정렬을 사용해서 풀 경우 매우 오랜 시간이 소요된다. 입력되는 수의 종류가 10000개 이하로 매우 적고, 입력되는 수가 1000만 개까지 되므로 int형 배열 10001개를 선언하여 인덱스를 기록하는 방식으로 진행하여야 한다.

1. int 배열 10001개를 선언한다.
2. 수를 입력 받는다.
3. 입력받의 수의 인덱스에 +1을 한다.
4. 입력이 종료될 때까지 2~3을 반복한다.
5. 1부터 배열에 입력된 수만큼 해당 수를 출력한다.

입출력이 각각 1000만 번씩 이루어지므로 입출력에 소요되는 시간을 최대한 줄여야 한다. 정렬이 아무리 빨라도 입출력이 오래 걸리면 시간 초과가 되기 때문. 빠른 입출력에 대해서는 15552번 문제 설명을 참고하도록 한다.

풀이 코드

#include <iostream>
using namespace std;

void BAEKJOON_10989()
{
	ios::ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int N;
	cin >> N;
	int index[10001] = { 0 };
	for (int i = 0; i < N; i++)
	{
		int temp;
		cin >> temp;
		index[temp]++;
	}
	for (int i = 1; i <= 10000; i++)
	{
		for (int j = 0; j < index[i]; j++)
		{
			cout << i << "\n";
		}
	}
	return;
}void BAEKJOON_번호()
{
	return;
}