문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬

조건

시간 제한 : 5 초
메모리 제한 : 8 MB

이전 문제
보다 시간은 늘었지만 메모리 제한이 급격히 줄어듦

입력

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

출력

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

풀이

try1

#include <iostream>
#include <algorithm>

using namespace std;

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

    int N;
    cin >> N;

    int arr[N];

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

    sort(arr, arr + N);

    for (int i = 0; i < N; i++)
    {
        cout << arr[i] << '\n';
    }

    return 0;
}

이전 문제와 동일하게 내장 sort 함수를 사용하였더니
-> 메모리 초과

try2

수의 개수의 최댓값이 10,000,000이지만, 입력받는 숫자의 경우의 수는 10000개밖에 안된다.

따라서 배열 전체를 정렬하기보다는
1부터 10000까지의 숫자가 각각 몇번 나오는지를 체크하고,
각 숫자를 횟수만큼 1부터 10000까지 순서대로 출력해준다.

즉, 수의 범위가 작다면 카운팅 정렬을 사용하여 더욱 빠르게 정렬할 수 있다.

#include <iostream>
#include <algorithm>

using namespace std;

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

    int N, num;
    cin >> N;

    int arr[10001];
    fill_n(arr, 10000, 0);

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

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

    return 0;
}

-> 출력 초과 (틀렸습니다와 같은 의미라고 함)

try3

도저히 이유를 알 수 없어 다른 분의 풀이를 보고

fill_n(arr, 10000, 0); -> fill_n(arr, 10001, 0); 로 바꿔줬다.

arr 선언시 크기를 10001로 했기 때문에 fill_n도 동일하게 맞춰줘야 하는 것 같다. (정확한 이유는 모르겠다..)

#include <iostream>
#include <algorithm>

using namespace std;

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

    int N, num;
    cin >> N;

    int arr[10001];
    fill_n(arr, 10001, 0);

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

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

    return 0;
}

Reference

https://cryptosalamander.tistory.com/46
https://tooo1.tistory.com/72