백준 10989: 수 정렬하기 3

 

www.acmicpc.net/problem/10989

10989번: 수 정렬하기 3

 

데이터의 개수 가 최대 10,000,000 개

시간 복잡도 O(N)의 정렬 알고리즘 필요

수위 범위가 1~10,000임으로 계수 정렬을 사용

메모리 제약은 8MB

 

#include <iostream>
#include <algorithm> // min
#include <functional>
#include <math.h>
#include <string>
#include <vector>

typedef unsigned long long ull;
using namespace std;

int table[10001] = { 0, };
int main() {

	ios::sync_with_stdio(false); cin.tie(0);  // scanf 안쓸 경우 쓰세요. Cin 사용시
	int n; cin >> n;

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

	for (int i = 0; i < 10001; i++) {
		int cand = table[i];
		for(int j=0;j<cand; j++)
			printf("%d\n", i);
	}
	
	return 0;
}