백준 10989 수 정렬하기 3 / C++

문제 : 10989

풀이 point

메모리 제한이 8MB이므로 평범하게 10,000,000범위를 모두 입력 받을 수는 없다.
대신 수의 제한이 1~10,000이기 때문에 이를 통해 풀수 있다.

입력받은 수가 2라면 인덱스 2의 값을 +1 해준다. 그러면 이 배열은 인덱스가 해당하는 숫자, 값이 해당하는 숫자의 빈도수가 된다.

풀이 방법

이중 for문을 통해 정렬된 결과를 도출하면 된다.
1이 5번 등장했다면 배열의 인덱스 1에 5가 저장되어있을 것이다.
a[1] = 5 그렇다면 1을 총 5번 출력해주면 된다.

코드

//백준 10989, 수 정렬하기 3

#include <iostream>
#include <algorithm>

int arr[10'001];

int main(){

    int N;
    std::cin >> N;
    for(int i{0}; i<N; ++i){
        int n;
        std::cin >> n;
        ++arr[n];
    }

    for(int i{1}; i<=10000; ++i){
        for(int j{1}; j<=arr[i]; ++j){
            std::cout << i << '\n';
        }
    }

    return 0;
}