[C++] 백준 10989번 수 정렬하기 3

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

풀이

수의 개수가 최대 10,000,000인데 메모리 제한이 8MB라서 입력받는 모든 수를 배열에 저장하려고 하면 메모리 초과가 발생한다.

대신 입력받는 수를 인덱스로 삼아서 그 수의 개수를 배열에 저장한다.
입력받는 수의 범위는 1 ~ 10,000이므로 메모리를 절약할 수 있다.

입력이 끝나면 배열의 처음부터 순회하면서 원소값의 수만큼 인덱스 값을 반복 출력하면 된다.

코드

#include <iostream>

using namespace std;

int main()
{
    int N, x;
    int cnt[10001] = {0};
    
    cin >> N;
    for(int i=0; i<N; i++) {
        cin >> x;
        cnt[x]++;
    }
    
    for(int i=1; i<10001; i++) {
        for(int j=0; j<cnt[i]; j++) {
            cout << i << "\n";
        }
    }
    
    return 0;
}