문제
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;
}