[백준 10989번] [배열과 수의 매칭] [빠른 입출력] 수 정렬하기 3

이 문제의 경우는 약간 독특하다.

일반적으로 오름차순으로 정렬하기 위해서는 가장 간단하게는 sort를 사용하면 되지만, 이 문제에서는 시간제한은 조금 널럴한 대신 메모리제한이 매우 제한적이다.

 

수가 10000으로 제한되어 있으므로 배열의 index와 숫자를 연결시켜서 저장시킨 뒤, 숫자가 들어오면 해당 배열의 값을 1 증가시키는 방식으로 메모리를 아낄 수 있음을 느끼고 문제를 접근했으면 된다.

 

위의 알고리즘으로 문제를 접근하면 다음과 같다.

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cstdlib>

using namespace std;

int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int n;
    cin >> n;
    
    vector<int> data_store(10001, 0);

    for(int i = 0; i < n; i++){
        int temp;
        cin >> temp;

        data_store[temp] += 1;
    }

    for(int i = 1; i < 10001; i++){
        for(int j = 0; j < data_store[i]; j++){
            cout << i << "\n";
        }
    }

    return 0;
}

추가적으로 입출력이 10000000으로 매우 많은 편이므로, 빠른 입출력을 해줘야지 시간초과를 면할 수 있다.