백준 10989 수 정렬하기 3

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

10989번: 수 정렬하기 3

 

 

EXPLANATION

 

입력값을 index로 가지고 그 원소가 이 index를 입력값으로 받은 횟수를 나타내는  배열을 생각한다.

 

예를 들어 아래와 같은 입력을 받았다고 하자.

5 2 3 1 4 2 3 5 1 7

그러면, 배열 input이 있을 때

input[1] = 2, input[2] = 2, input[3] = 2, input[4] = 1, input[5] = 2, input[7] = 1이 된다.

 

그럼 input배열의 index를 오름차순으로 나열할 때 2중 for 문으로 그 원소의 수만큼 나열해주면된다.

 

 

 

그런데 그냥 코드를 작성하니 시간 초과가 되어 다음과 같은 코드를 작성하여 실행속도를 높여 시간을 단축시켰다.(설명)

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

 

 

CODE

#include <iostream>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);


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