백준 10989번 수 정렬하기 3(C++)

문제 해결 방안 : 카운트 정렬 이용

문제 해결 소감 : 다른 수 정렬하기 문제와 차이점은 시간은 널널하게 주고 메모리 사용량은 평균보다 작게 제한했다는 것이다. 처음에는 벡터와  std::sort를 사용했는데 최대 천만개인 요소들을 모두 담기에는 용량이 부족했다. 방법을 찾아보던 중 카운트 정렬이라는 정렬 알고리즘을 알았고 이를 이용해서 풀었다. 이전에는 같은 방법을 사용했는데 그것이 카운트 정렬이라는 것을 알았다.

#include <iostream>

int main()
{

    int N;
    std::cin >> N;

    int arr[10001] = {0};

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

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

    return 0;
}