백준 10989번: 수 정렬하기 3

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

1. 문제

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

2. 알고리즘

키워드 - 정렬

메모리 제약사항이 8MB 이고 들어오는 입력으로 들어오는 숫자가 10000000 개 임으로 일반적인 sort 함수를 사용해서는 풀 수 없다.

입력으로 들어오는 숫자의 상한 값이 10000 이상 입력되지 않기 때문에 모든 수를 메모리에 적제할 필요는 없다.

10000 * 4 = 4만 바이트에 용량으로 처리가 가능하다.

3. 코드

#include <iostream>
#include <algorithm> // min
#include <functional>
#include <math.h>
#include <string>
#include <vector>
 
typedef unsigned long long ull;
using namespace std;
 
int dp[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;
        dp[nn]++;
    }
 
    for (int i = 0; i < 10001; i++) {
        int cand = dp[i];
        for(int j=0;j<cand; j++)
            printf("%d\n", i);
    }
    
    return 0;
}