10989번 수 정렬하기3 / C++ → 카운팅 정렬(Counting Sort)로 풀기

10989번 수 정렬하기 3 -> https://www.acmicpc.net/problem/10989

카운팅 정렬(Counting Sort) 혹은 기수정렬(Radix Sort)를 사용해 정렬을 하는 문제이다.

라딕스정렬도 재밌어보였지만 카운팅소트가 더 쉬워보여서 이걸로 구현하였다.

라딕스 정렬이 궁금하신분은 이 영상을 참고 -> https://www.youtube.com/watch?v=xuU-DS_5Z4g

쉽게말하면 1의자리부터 정렬하고 그다음 10의자리 정렬, 100의자리 정렬, ... 반복하여 정렬하는 것이다.

카운팅 정렬은 해당숫자가 몇번 나오는지를 카운팅하여 그 숫자의 자리를 찾아주는 식으로 정렬한다.

예를들어 아래와 같은 데이터가 있다고하면

3

2

1

5

0

8

6

6

2

1

1. 해당 숫자가 몇번 나왔는지 카운팅을 한다.

0	1	2	3	4	5	6	7	8
1	2	2	1	0	1	2	0	1

2. 앞자리부터 카운팅을 누적하여 해당 숫자의 자리를 찾아준다.

(오름차순으로 정렬할 것이기 때문에 작은수부터 나오게 될 것이고, 앞의 수의 개수가 지나면 다음 수가 나올 것이다.)

0	1	2	3	4	5	6	7	8
1	3	5	6	6	7	9	9	10

3. 처음의 데이터를 다시 탐색하면서 누적한 데이터에서 해당 자리를 찾아 넣어준 후 데이터의 값을 하나 빼준다.

3

2

1

5

0

8

6

6

2

1

-> 3이면 누적데이터에서 6이니까 6번째자리에 넣고 -1하여 5를 넣어준다.

-> 2는 5번째자리에 넣고 -1하여 4를 넣어준다.

-> 1은 3번째자리에 넣고 -1하여 2를 넣어준다.

.. 반복하면 모든 값이 정렬된다.

그림으로 그리면 이런 식으로 진행이 된다.

처음에는 아래처럼 데이터를 입력받아 배열에 저장하고

카운팅하는 배열, 카운팅을 누적하는 배열, 정렬한 배열을 만들어 작성했으나 제출하니 런타임 에러가 발생했다.

#include <iostream>
using namespace std;
 
main()
{
    cin.tie(NULL);
    int num;
    cin >> num;
 
    int* data = new int[num];
    int max = 0;
    for (int i = 0; i < num; i++)
    {
        int d;
        cin >> d;
        data[i] = d;
 
        if (data[i] > max)
            max = data[i];
    }
 
    int* count = new int[max+1];
    fill_n(count, max + 1, 0);
    for (int i = 0; i < num; i++)
    {
        count[data[i]]++;
    }
 
    
    int* count2 = new int[max + 1];
    fill_n(count2, max + 1, 0);
    for (int i = 0; i < max+1; i++)
    {
        if (i == 0)
            count2[i] = count[i];
        else
            count2[i] = count2[i - 1] + count[i];
    }
 
    int* sort = new int[num];
    for (int i = num-1; i >= 0; i--)
    {
        int k = count2[data[i]] - 1;
        count2[data[i]]--;
        sort[k] = data[i];
    }
 
    for (int i = 0; i < num; i++)
        cout << sort[i] << endl;
 
    delete[] data;
    delete[] count;
    delete[] count2;
    delete[] sort;
}

그래서 질문을 찾아보다 보니 메모리 제한이 8MB였다.

데이터가 최대 1000만개가 주어지니 동적할당하면 메모리가 부족해서 일어난 문제였다.

#include <iostream>
using namespace std;
 
main()
{
    cin.tie(NULL);
    int num;
    cin >> num;
 
    int count[10001];
    fill_n(count, 10001, 0);
 
    for (int i = 0; i < num; i++)
    {
        int d;
        cin >> d;
        count[d]++;
    }
    
    for (int i = 0; i < 10001; i++)
    {
        if (i != 0)
            count[i] += count[i - 1];
    }
 
    for (int i = 0; i < 10001; i++)
    {
        if (i == 0)
        {
            if (count[i] != 0)
                cout << count[i] << endl;
        }
        else
        {
            if (count[i - 1] != count[i])
            {
                for (int j = 0; j < (count[i] - count[i - 1]); j++)
                {
                    cout << i << endl;
                }
            }
        }
    }
}

그래서 입력값을 할당하지않고 바로 카운트하기로 결정하였고

입력의 최대값이 10000이므로 그냥 10001개짜리의 배열을 만들었다.

이후 데이터를 입력받을때마다 배열에서 바로 카운팅하였고

누적값도 배열의 처음부터 앞의값과 더해가면서 기존 배열을 이용해 덮어씌웠다.

그리고 첫값이 0이아니면 출력하고, 이후 앞의값과 뒤의값을 비교해 값이 달라질때만(입력받은 데이터가 있을때만)

해당값을 바뀐수치만큼 출력하였다.

이렇게 제출하니 메모리문제는 해결되어 런타임에러는 안나는데 시간초과가 출력되어

endl대신 \n을 사용하니 시간초과가 해결되었다.