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

문제

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

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.

출력

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

구상

단계별로 풀어보기 - 정렬 단계로 들어가면 카운팅 정렬을 활용해보자고 한다. 카운팅 정렬을 통해 해결해보자.

카운팅 정렬(counting sort)는 계수 정렬이라고도 한다. 각 숫자의 개수를 세서 $1$을 $a$개, $2$를 $b$개, $3$을 $c$개... 순차적으로 저장하여 정렬하는 방식이다.

우선 수의 개수 $N$의 범위가 $1\leq N \leq 10,000,000$로 매우 넓으므로 초기값을 입력받을 배열은 동적 할당으로 선언한다.

 int inputSize;  //입력 배열의 크기
 int* inputArray = (int*)malloc(sizeof(int) * inputSize);    //입력 배열

이 배열에 저장된 값은 다음과 같다고 하자.

다음으로 inputArray에 저장된 각 숫자의 개수를 저장할 카운팅 배열이 필요하다.

이 배열의 크기는 'inputArray에 저장된 정수 중 가장 큰 값+1'로 한다. 

countingArray의 인덱스 그 자체가 어떤 숫자인지를 알려주는 역할이고, 대응하는 요소가 그 숫자의 개수를 알려주는 역할이다.

1이 1개 있으면 countingArray[1] = 1이다.

3이 2개 있으면 countingArray[3] = 2이다.

 

인덱스는 0부터 시작하니 inputArray의 최댓값이 9라면 배열의 크기를 10으로 해서 인덱스를 9까지 만들어주는 것이다.

 

//카운팅 배열의 크기 정하기
int cntArrSize;

    //입력 배열의 최댓값+1이 카운팅배열의 크기
    for (i = 0; i < inputSize - 1; i++) {
        if (inputArray[i] < inputArray[i + 1])
            cntArrSize = inputArray[i + 1];
        else
            cntArrSize = inputArray[i];
    }
    
//카운팅 배열 생성
int* countingArray = (int*)calloc((cntArrSize + 1), sizeof(int));

카운팅 배열을 활용하려면 한번 더 가공해야 한다.
위 배열에서 3은 몇 번째 인덱스까지 차지하는 것일까?

{1, 2, 3, 3}이므로 4번째 인덱스, [3]까지 차지한다. 이 정보를 얻어내기 위해서 countingArray의 첫 요소부터 끝 요소까지 누적해서 더해준다. 

0은 없으니 0이고, 1은 1번까지, 2는 2번까지, 3은 4번까지, 4도 없으니 4번까지다.

//이전 요소의 값을 누적해서 더하기(위치 정하기)
    for (i = 1; i <= cntArrSize; i++) {
        countingArray[i] += countingArray[i - 1];
    }

이제 정렬된 값을 저장할 새로운 배열을 선언하고 값을 정렬할 차례다.

//정렬된 값을 저장할 배열
    int* alignedArray = (int*)calloc(inputSize, sizeof(int));
    for (i = inputSize - 1; i >= 0; i--) {
        int j = inputArray[i];
        countingArray[j] -= 1;
        alignedArray[countingArray[j]] = inputArray[i];
    }

값은 역순으로 읽어나간다.

inputArray[9] = 1을 어디다 넣어야 할까? 첫 번째 1이니 alignedArray[0]에 넣어야 한다.

for (i = inputSize - 1; i >= 0; i--) {
        int j = inputArray[i];

1을 사용했다는 것을 알리기 위해 countingArray[1]의 값을 하나 빼주고,

countingArray[j] -= 1;

alignedArray[0]에 값을 대입한다.

alignedArray[countingArray[j]] = inputArray[i];

 

 

코드

일반적인 카운팅 배열

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

int main(void)
{
    int i;  //반복 제어 변수
    int inputSize;  //입력 배열의 크기
    scanf("%d", &inputSize);
    int* inputArray = (int*)malloc(sizeof(int) * inputSize);    //입력 배열
    //입력 배열에 값 입력
    for (i = 0; i < inputSize; i++) {
        scanf("%d", &inputArray[i]);
    }

    int cntArrSize; //카운팅배열의 크기

    //입력 배열의 최댓값+1이 카운팅배열의 크기
    for (i = 0; i < inputSize - 1; i++) {
        if (inputArray[i] < inputArray[i + 1])
            cntArrSize = inputArray[i + 1];
        else
            cntArrSize = inputArray[i];
    }
    //카운팅 배열 생성
    int* countingArray = (int*)calloc((cntArrSize + 1), sizeof(int));
    //카운팅 배열 요소 채우기
    for (i = 0; i < inputSize; i++) {
        countingArray[inputArray[i]] += 1;
    }

    //이전 요소의 값을 누적해서 더하기(위치 정하기)
    for (i = 1; i <= cntArrSize; i++) {
        countingArray[i] += countingArray[i - 1];
    }
    //정렬된 값을 저장할 배열
    int* alignedArray = (int*)calloc(inputSize, sizeof(int));
    for (i = inputSize - 1; i >= 0; i--) {
        int j = inputArray[i];
        countingArray[j] -= 1;
        alignedArray[countingArray[j]] = inputArray[i];
    }

    //출력
    for (i = 0; i < inputSize; i++) {
        printf("%d\n", alignedArray[i]);
    }

    //메모리 할당 해제
    free(inputArray);
    free(countingArray);
    free(alignedArray);

    return 0;
}

그런데 이렇게 하면 메모리 초과 오류가 발생한다.

문제에서 제한한 최대 메모리는 8MB이다.
하지만 이렇게 배열을 동적할당해서 문제를 해결하면, 수가 최대치인 천 만개 입력될 경우 int값 정수 천 만개를 저장하는 배열이 만들어진다. 이미 메모리를 한참 초과한 상태인 것이다.

그래서 입력값을 모두 저장해두는 배열을 사용하면 안 된다.
숫자의 개수만 저장하는 배열을 만들어서 카운팅 정렬의 개념만 이용하면 메모리 초과 이슈 없이 문제를 해결할 수 있다.

메모리 초과 해결

int main(void) 
{
    int countingArr[10001] = { 0 }; //입력 배열
    int inputSize;  //입력 배열의 크기
    int num;    //입력받는 수

    scanf("%d", &inputSize);\
    
    //각 숫자의 개수만 세서 저장하기
    for (int i = 0; i < inputSize; i++) {
        scanf("%d", &num);
        countingArr[num] += 1;
    }
	
    //각 숫자를 저장된 개수만큼 출력하기
    for (int i = 1; i < 10001; i++) {
        for (int j = 0; j < countingArr[i]; j++)
            printf("%d\n", i);
    }

    return 0;
}