[백준] 수 정렬하기 3 10989번 문제풀이

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

10989번: 수 정렬하기 3

문제

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

입력

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

출력

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

 

이문제는 N의 갯수가 상당히 크네요. 그렇기 때문에 퀵정렬이나 병합정렬을 사용하지 않고 

계수 정렬을 사용하여 문제를 풀어보겠습니다. 

계수정렬을 잘 모르신다면 아래 글을 읽어보시기 바랍니다. 

 

https://modernalchemist.tistory.com/31

[자료구조] counting sort 계수정렬

간단한 소스인데요 

배열에 숫자를 입력받고 

배열에 들어가 있는 값만큼 숫자를 출력해주면 됩니다. 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>

int n, m; 
int a[10001];

int main() {
	scanf("%d ", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d ", &m);
		a[m]++;
	}
	for (int i = 0; i < 10001; i++) {
		while (a[i] != 0) {
			printf("%d \n", i);
			a[i]--;
		}
	}
}