[정렬 단계] 백준 10989번 수 정렬하기3

문제

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

입력

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

출력

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

 

메모리 제한이 8MB이기 때문에 10000000의 배열을 담을 수 없다. 

현재 입력 값의 범위가 주어졌기 때문에 계수 정렬을 이용한다.

10000의 배열에 각 수가 몇번 등장했는지 카운트하고 앞에서부터 카운트 된게 있는 인덱스에 대해서 출력하면 끝.

 

하지만 만약 값의 범위가 크다면 1,3,10000 이렇게 입력 값이 주어졌다면 1부터 10000까지 순회해야하는 불편함이 있기 때문에 누적합을 구한뒤 기존 배열의 뒷 수부터 누적합 위치에서 해당 수를 출력하고 값을 1씩 깎으면서 다음 인덱스를 만들면 된다.

그런데 이 문제는 애초에 100000000의 배열을 만들 수 없으므로 위 로직은 사용 불가.

#include <iostream>
#include <vector>
#include <string>
#include<algorithm>
using namespace std;

int N;
int cnt[10001];
int main(){

	
	cin >> N;
	//입력 값 카운트
	for (int i = 0; i < N; i++)
	{
		int a;
		scanf("%d", &a);
		cnt[a]++;
	}
	
	for (int i = 1; i <= 10000; i++)
	{
		if (cnt[i])
		{
			for (int j = 0; j < cnt[i]; j++)
			{
				printf("%d\n", i);
			}
		}
	}
}