chaetudy

문제

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

입력

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

출력

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

• 메모리 초과

 배열 원소의 개수가 10,000,000개임에도 불구하고 메모리 제한이 8mb이다. 모든 입력을 배열에 저장하면 당연히 메모리 초과일 것이다. int형이 아닌 short형으로 저장하여도 개수가 워낙 많아 부지기수이다.

 10,000,000개의 입력을 전부 저장하지 않는 방법은 없을까? 힌트는 수의 범위 안에 있다.

• 해결

 입력으로 들어온 수를 value로 저장할 것이 아니라 key의 개념으로 보아야 한다. 즉, 5가 들어오면 arr[5]의 값을 1 늘려 주는 식으로 한다. 이렇게 하면 10,000,000개의 모든 입력을 전부 저장하지 않아도 무슨 수가 몇 개 있는지 알 수 있다.

#include <iostream>
using namespace std;

int main(void){
	ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n, nArr[10001] = {0}, input;
    cin >> n;
    for(int i = 0; i < n; ++i){
    	cin >> input;
        nArr[input]++;
    }
    for(int i = 0; i < 10001; ++i){
    	if(nArr[i] > 0){
        	for(int j = 0; j < nArr[i]; ++j){
            	cout << i << "\n";
            }
        }
    }
}