BOJ 10989, 수 정렬하기 3

말 그대로 수를 정렬하는 문제입니다. 

문제의 조건을 잘 읽어보면, N이 10,000,000이라 O(NlgN)의 정렬 방법을 사용하면 시간 안에 풀 수 있을거라는 추측을 할 수 있습니다.

하지만, 문제의 메모리 사용 조건이 8MB이기에, 1000만개의 수를 모두 배열 안에 저장할 수는 없습니다.

그럼 어떤 방법을 생각할 수 있을까요?

문제에서 제시하는 수의 범위를 유심히 살펴봐야 합니다.

입력이 1000만개가 주어지는데, 입력으로 주어지는 수는 1부터 1만까지밖에 없습니다. 1만개를 초과하는 수가 입력으로 주어지면, 비둘기 집의 원리(서랍원리?)에 의해 반드시 중복이 존재할 수 밖에 없습니다.

따라서, 모든 수를 배열에 저장하는게 아닌

수의 개수를 길이가 10000인 배열에 저장하면 됩니다.

입력이 종료된 다음, 배열을 전부 순회하면서 1이 3개라면 1을 3번 출력, 2가 2개라면 2를 2개 출력, 3이 0개면 출력을 하지 않고, 4가 2개면 4를 2번 출력 ... 하면 됩니다

아래는 그 소스코드입니다.

#include <cstdio>
int arr[10010] = { 0, };
 
int main() {
    int n;
    scanf("%d", &n);
 
    for (int i = 0; i < n; i++) {
        int temp;
        scanf("%d", &temp);
        arr[temp]++;
    }
 
    for (int i = 0; i < 10001; i++) {
        while (arr[i]--) {
            printf("%d\n", i);
        }
    }
 
    return 0;
}