백준_10989_수정렬하기3(counting sort)

 

숫자를 정렬하는 간단한 문제처럼 보이지만, 메모리 제한이 8mb로 매우 작기 때문에 이때까지와는 다른 방식으로 풀어야 합니다.

 

입력을 보시면 데이터가 천만개 까지 들어올 수 있는데, int 형 1천만개를 배열에 넣으면 8mb를 넘어가기 때문에

배열에 넣고 정렬하는 방밥은 쓰면 안됩니다.

 

이번에 써볼 정렬 방식은, 시간 복잡도가 작은 계수정렬(counting sort) 입니다.

 

 

계수정렬)

계수 정렬이란, 비교 연산을 하지 않는 정렬 방식입니다.

 

배열 내에 특정한 값이 몇 번 등장했는지를 세서 정렬을 수행하는 방식이기 때문에 속도가 보장됩니다.

 

최악의 경우라도, 시간 복잡도가 O(n+k) 로 매우 작습니다.

 

아래 그림을 보며 어떻게 정렬되는지 확인해봅시다.

 

 

 

정렬 방식)

---

다음과 같은 array1 배열이 있을 때 특정 값이 몇 개 있는지 저장할 두 번째 배열을 만들어줍니다.

array1 { 5 , 2 , 3 , 1 , 4 , 2 , 3 , 5 , 1 , 7 }

 

array2.   // 1번 인덱스에는 array1 에 있는 1의 개수, 이런식으로 숫자의 개수가 들어가게 됩니다.

0	2	2	2	1	2	0	1	0	0
[0]	[1]	[2]	[3]	[4]	[5]	[6]	[7]	[8]	[9]

 

array2를 만드실 때 주의해야 할 점이 있습니다.

 

위의 배열들을 보면, array1의 최대값은 7입니다.

그렇기에, array2에서는 인덱스가 7이 넘어가면 모두 0이 들어가니 필요가 없겠죠.

 

그래서, max를 array1의 최대값이라고 한다면, array2[max+1] 로 선언해줘야 합니다.

그럼 이제, array2에 있는 정보를 가지고 출력만 해주면 됩니다!

 

하지만, 이 문제는 위의 과정을 조금 변형해야 합니다. (메모리 문제 때문에....)

 

코드를 보면 간단하게 이해하실 수 있습니다.

 

 

배열 선언 및 값 삽입 코드)

int n;
scanf("%d", &n);

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

    b[a]++;
}

 

우선, a를 배열로 선언하지 않고 int형 변수로 선언하였습니다.

 

만약 이 값이 1천만개 들어온다면, 이 문제에서 메모리 초과가 발생하기 때문입니다.

 

그래서 하나 입력받아 하나 처리한다는 느낌으로 정수 a를 입력받아 b배열에 정보를 저장하는 방식으로 처리했습니다.

 

 

배열 b의 크기를 1백만으로 설정한 이유는, a를 배열로 입력받는 것이 아니라 정수로 입력받기 때문에 최대값을 찾기 힘들고, 

 

a로 입력받을 수 있는 최대값이 1백만이기 때문입니다.

(반복문 하나로 깔끔하게 하기 위함도 있습니다..ㅎㅎ)

 

 

 

출력 코드)

for (int i = 0; i < 1000000;)
{
    if (b[i] == 0)
    {
        i++;
    }
    else
    {
        for (int j = b[i]; j > 0; j--)
        {
            printf("%d\n", i);
        }
        i++;
    }
}
printf("\n");

 

출력 코드는 간단합니다.

 

b배열에는 각 숫자가 몇 번 들어가있는지가 저장되어 있기 떄문에, 작은 수부터 차례대로 출력해주기만 하면됩니다.

 

같은 수가 여러번 있을 수도 있으므로, 배열의 값이 0이 될때까지 출력해줍니다.

 

 

 

 

 

전체 코드)

#include <stdio.h>

int main(void)
{
    int n;
    scanf("%d", &n);

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

        b[k]++;
    }
    for (int i = 0; i < 1000000;)
    {
        if (b[i] == 0)
        {
            i++;
        }
        else
        {
            for (int j = b[i]; j > 0; j--)
            {
                printf("%d\n", i);
            }
            i++;
        }
    }
    printf("\n");
    return 0;
}

 

 

이렇게 하면, 메모리 초과 없이 잘 실행되는 것을 확인할 수 있습니다.

 

 

 

 

 

 

오답)

#include <stdio.h>

int max_num(int a[], int size);
void counting_sort(int a[], int b[], int c[], int max, int size);

int main(void)
{
    int n;
    scanf("%d", &n);

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

    int size = sizeof(a) / sizeof(int);
    int max = max_num(a, size);

    int b[max + 1];
    int c[n];

    counting_sort(a, b, c, max, size);
}

int max_num(int a[], int size)
{
    int max = 0;
    for (int i = 0; i < size; i++)
    {
        if (a[i] > max)
        {
            max = a[i];
        }
    }
    return max;
}

void counting_sort(int a[], int b[], int c[], int max, int size)
{
    for (int i = 0; i <= max; i++)
    {
        b[i] = 0;
    }

    for (int i = 0; i <= max; i++)
    {
        for (int j = 0; j < size; j++)
        {
            if (a[j] == i)
            {
                b[i]++;
            }
        }
    }

    for (int i = 1; i <= max; i++)
    {
        b[i] = b[i] + b[i - 1];
    }

    for (int i = size - 1; i >= 0; i--)
    {
        c[b[a[i]] - 1] = a[i];
        b[a[i]]--;
    }

    for (int i = 0; i < size; i++)
    {
        printf("%d\n", c[i]);
    }
    // printf("\n");
}

 

 

이 코드는 카운팅 정렬의 심화 버전입니다.

a를 정수로 입력받지 않고 배열로 입력받고, b,c 배열을 만들어 개수를 세며 정렬을 해나가는 방식인데,

이 문제에서는 메모리 문제 때문에 사용할 수 없습니다..

 

그래도 작동은 잘 합니다!

 

처음에는 이렇게 코드를 짰다가 메모리 문제때문에 고민 꽤나 했는데

 

위의 코드처럼 간단하게 해결되어서 다행입니다ㅎㅎ