[C++] 백준 10989번 - 수 정렬하기 3 (메모리 초과 주의)

문제 링크 : https://www.acmicpc.net/problem/10989

10989번: 수 정렬하기 3

 

 

문제

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

입력

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

출력

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

 

 

---

 

접근 방법

수 정렬하기 1번과 2번은 vector의 sort()로 쉽게 풀었는데 이번 문제는 N의 범위가 커서 메모리 초과가 난다.

우선순위 큐를 써도 똑같이 메모리 초과가 난다.

그래서 수의 범위가 10,000을 넘지 않는 점을 고려해서 아래와 같이 코드를 작성했다.

 

* 참고

   ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

를 쓰지 않으면 시간초과가 뜬다. 

 

 

#include <iostream>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int N; cin >> N;
    int arr[10001] = {0,};
    int num =0;
    for(int i = 0; i<N; i++){
        cin >> num;
        arr[num] += 1;
    }
    for(int i = 1; i<=10000; i++){
        for(int j = 0; j<arr[i]; j++){
            cout << i << "\n";
        }
    }
    
    return 0;
}