백준 10989번 C언어 풀이

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

10989번: 수 정렬하기 3

정수를 정렬하는 문제. 수 정렬하기2(https://www.acmicpc.net/problem/2751)는 시간을 적게준 대신에 메모리는 넉넉하게 줬다면, 이번에는 시간을 좀 널널하게 주는 대신에 메모리를 확 줄여버린 문제이다. 처음에는 그게 무슨상관이지? 했는데, 메모리를 적게 준데에는 다 이유가 있었던거 같다.

 

수 정렬하기 2도 퀵소트로 풀려다가 못풀어서 결국 C의 stdlib헤더의 qsort와 C++의 std::sort로 겨우 풀긴 했었지만, 이번에는 그것도 먹히지 않는다. 아무래도 다른 정렬알고리즘로 해결을 해야 할 것 같다.

 

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

int compare(const void *a, const void *b)
{
    int num1 = *(int *)a;
    int num2 = *(int *)b;

    if (num1 < num2) return -1;
    if (num1 > num2) return 1;
    return 0;
}

int main () {
    int * arr = NULL;
    int len;
    scanf("%d", &len);
    arr = (int *)malloc(sizeof(int) * len);
    for (int i = 0; i < len; i++)
        scanf("%d", &arr[i]);

    qsort(arr, len, sizeof(int), compare);
    for (int i = 0; i < len; i++)
        printf("%d\n", arr[i]);
    free(arr);
}

 

// C++
#include <iostream>
#include <algorithm>

using namespace std;

int main () {
    int * arr;
    int len, i;
    cin >> len;

    arr = new int[len];
    
    for (i = 0; i < len; i++) cin >> arr[i];
    sort(arr, arr+len);
    for (i = 0; i < len; i++) cout << arr[i] << '\n';
}

 

21.11.06. 사진 수정

-------------------------------------------------- 21. 11. 23 --------------------------------------------------

 

기존의 방식으로 해결을 하는 경우 메모리가 초과가 되었다. 기존의 방식은 일단 입력받은 모든 수를 저장을 한 후에, 정렬을 하는 방식이었기 때문이다. 검증케이스에는 최대 천만개의 정수가 들어오게 되는데, 이때 이 수를 모두 저장하는 경우, 4천만 바이트, 약 40MB를 수를 저장하는데 사용하게 된다. C계열의 메모리 제한이 8MB임을 보면, 기준치를 5배나 넘기는 셈이다. 이러니 메모리가 초과될 수 밖에...

 

이러한 문제를 어떻게 해결할까 하다가, 단계별 풀이의 힌트(https://www.acmicpc.net/step/9)를 보고 카운팅 정렬이라는 알고리즘을 알게 되었다. 카운팅정렬의 큰 틀은, 입력받은 수를 저장하는게 아니라, 몇번 등장했는지를 저장하여, 등장횟수의 배열을 누적합으로 바꾸고, 이를 이용하여 정렬하는 알고리즘이다.

 

이 알고리즘에서 방법을 착안하여, 필자는 숫자들의 등장횟수만을 세고, 반복문을 돌면서, 등장횟수만큼 숫자를 출력하는 방식으로 해결했다. 굳이 누적합을 하여 재배열하는 단계가 필요없을 것이라고 판단했기 때문이다.

 

이 방식의 단점은, 갑자기 큰수가 확 나와버리면 무의미한 반복문을 돌기 때문에 입력되는 숫자의 범위를 잘 보아야 한다.

 

#include <stdio.h>
#define SIZE 10000

int main () {
    int count[SIZE] = {0};
    int t, input;

    scanf("%d", &t);
    while(t--) {
        scanf("%d", &input);
        count[input-1]++;
    }

    for (int i = 0; i < SIZE; i++) {
        for (int j = 0; j < count[i]; j++) {
            printf("%d\n", i+1);
        }
    }
}