[10989] 수 정렬하기 3

[10989] 수 정렬하기 3

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

• 시간제한 3초
• 메모리 제한 8MB

입력

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

출력

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

코드

#include <iostream>

using namespace std;

int main() {
    static int N, count[10001] = {0, };
    scanf("%d", &N);

    // 입력 받고 count해줌
    for(int tmp, i = 0; i < N; i++) {
        scanf("%d", &tmp);
        count[tmp]++;
    }

	// count된 개수 만큼 출력
    for(int i = 0; i < 10001; i++)
        for(int j = count[i]; j > 0; j--)
            printf("%d\n", i);
}

아래는 counting sort를 구현하여 배열을 sort하는 코드이다.
메모리 초과로 실제로 배열을 정렬하지는 못해 위의 코드를 사용하여 제출했다.

#include <iostream>
#include <vector>

using namespace std;

int main() {
    static int N, count[10001] = {0, };
    scanf("%d", &N);
    vector<int> arr, sorted(N);

    // 입력 받고 count해줌
    for(int tmp, i = 0; i < N; i++) {
        scanf("%d", &tmp);
        arr.push_back(tmp);
        count[tmp]++;
    }

    // count array 누적합으로 만들어 줌
    for(int i = 1; i < 10001; i++)
        count[i] = count[i-1] + count[i];

    // 재배열
    for(int i = 0; i < N; i++)
        sorted[--count[arr[i]]] = arr[i];

    for(int i = 0; i < N; i++)
        printf("%d\n", sorted[i]);
}

부가 설명

위에는 코드가 총 2가지가 있다.
첫번째 코드는 실제로 제출한 코드이고, 두번째 코드는 제출 전 counting sort를 구현한 코드이다.
두번째 코드를 제출하면 최대 메모리인 8MB를 초과하므로 실제로는 정렬하지 않고 count만 하여 개수만큼 오름차순으로 출력해주는 코드로 제출했다.

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