[백준 C언어] 10989. 수 정렬하기 3

문제

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

입력

 

첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다.

이 수는 10,000보다 작거나 같은 자연수이다.

출력

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

 

 

나의 풀이 1. (메모리 초과 - 오답)

#include <stdio.h>
#include <stdlib.h>

int cmp(const void* a, const void* b) {
    return (*(char*)a - *(char*)b);

}

int main(void) {

    int n;
    char *arr;
    scanf("%d", &n);
    arr = (char*)malloc(sizeof(char) * n + 1);
    arr[n] = '\0';

    for (int i = 0; i < n; i++) {
        scanf("\n%c", &arr[i]);
    }


    qsort(arr, n, sizeof(char), cmp);

    for (int i = 0; i < n; i++) {
        printf("%d\n", arr[i]-'0');
    }

    free(arr);

    return 0;
}

 

일반적으로 떠올릴 수 있을 만한, 동적배열에 qsort를 활용한 정렬이다. 

처음에 size를 int로 주었는데 메모리 초과가 떠서 char로 바꾸어 봐도 동일한 문제가 발생했다.

 

생각해 보니 문제에서 주어진 메모리 제한이 8mb인데, 배열의 최대 요소 개수가 10,000,000개이므로 

char를 요소로 하는 10,000,000칸의 배열의 경우 10MB를 잡아먹는다...

이 방식으로 할 경우 메모리 사이즈를 int로 주든 char로 주든 당연히 메모리 초과가 나올 수밖에 없다. 

그래서 다음과 같이 코드를 바꾸었다. 

 

나의 풀이 2

#include <stdio.h>

int main(void) {

    int n, a, arr[10001] = { 0 };
    scanf("%d", &n);

    for (int i = 0; i < n; i++) {
        scanf("%d", &a);
        arr[a]++;
    }

    for (int i = 1; i <= 10000; i++) {
        if (arr[i] != 0)
            for (int j = 0; j < arr[i]; j++) 
                printf("%d\n", i);

    }

    return 0;
}

 

주어지는 수의 범위는 10000까지의 자연수이므로, 

배열을 이용하여 카운팅하는 방식을 활용했다. 

수를 n개만큼 입력받으면서 입력되는 수를 카운팅한 후, 

수가 입력된 개수만큼 배열 요소를 출력해주면 끝. 

별도로 배열을 만들어 정렬할 필요가 없는 문제였다.