백준 10989번 문제는 "수 정렬하기 3"이라는 문제로, 여러 개의 숫자를 입력받아 그 숫자들을 오름차순으로 정렬하는 문제입니다. 하지만 이 문제는 입력되는 숫자의 개수가 매우 많기 때문에, 효율적인 방법을 사용해야 합니다. 초등학생도 이해할 수 있도록 쉽게 설명해보겠습니다.
문제 이해하기
상상해 보세요, 여러분이 많은 카드를 가지고 있다고 합니다. 각 카드에는 1부터 10,000까지의 숫자 중 하나가 적혀 있습니다. 여러분의 임무는 이 카드들을 숫자가 작은 순서대로 빠르게 나열하는 것입니다.
문제의 접근 방법
이 문제를 해결하기 위한 방법 중 하나는 "계수 정렬(Counting Sort)"이라는 기법을 사용하는 것입니다. 이 방법은 숫자들의 개수를 세어 정렬하는 방식으로, 크기를 비교하는 정렬 방식과는 다릅니다. 이 방법을 사용하면 매우 빠르게 정렬할 수 있습니다.
1단계: 숫자 세기
1부터 10,000까지의 숫자에 대해 각 숫자가 몇 번 나왔는지 세야 합니다. 이를 위해, 각 숫자를 세는 배열을 만듭니다. 처음에는 모든 숫자가 0번 나왔다고 기록합니다.
입력받은 숫자를 하나씩 보면서, 그 숫자에 해당하는 배열의 위치의 값을 1씩 증가시킵니다. 예를 들어, 숫자 5를 입력받으면, 배열의 5번째 위치의 값을 1 증가시킵니다.
2단계: 정렬된 숫자 만들기
이제 배열을 앞에서부터 끝까지 확인하면서, 각 숫자가 몇 번 나왔는지 확인합니다.
만약 어떤 숫자가 1번 이상 나왔다면, 그 숫자를 그 횟수만큼 출력합니다. 예를 들어, 숫자 3이 2번 나왔다면, 숫자 3을 2번 출력합니다.
예시
입력된 숫자들: 5, 2, 3, 1, 4, 5
1단계에서 배열을 만들고 숫자를 센 후: 1이 1번, 2가 1번, 3이 1번, 4가 1번, 5가 2번 나왔습니다.
2단계에서 이 배열을 사용해 숫자를 출력하면: 1, 2, 3, 4, 5, 5
코드 작성 팁
초등학생도 이해할 수 있도록 코드를 작성할 때는 다음과 같은 팁을 따라보세요:
큰 숫자들을 세기 위한 충분히 큰 배열을 준비하세요.
입력받은 숫자를 이용해 배열에서 해당 숫자의 위치를 찾아 그 값을 증가시키세요.
배열을 처음부터 끝까지 확인하면서, 숫자가 나온 횟수만큼 그 숫자를 출력하세요.
이 방법을 사용하면, 매우 많은 숫자들도 빠르게 정렬할 수 있습니다. 계수 정렬은 숫자들의 범위가 작고, 숫자들이 많을 때 매우 효율적인 방법입니다.
정답코드
#include <stdio.h>
int main() {
int n, i, j;
int count[10001] = {0,}; // 1부터 10000까지의 숫자를 세기 위한 배열, 모든 값을 0으로 초기화
scanf("%d", &n); // 사용자로부터 숫자의 개수를 입력받음
// 입력받은 숫자를 세어 count 배열에 기록
for(i = 0; i < n; i++) {
int num;
scanf("%d", &num); // 숫자를 하나씩 입력받음
count[num]++; // 해당 숫자의 등장 횟수를 1 증가
}
// 정렬된 숫자 출력
for(i = 1; i <= 10000; i++) { // 1부터 10000까지 각 숫자에 대해
if(count[i] > 0) { // 해당 숫자가 한 번 이상 등장했다면
for(j = 0; j < count[i]; j++) { // 등장 횟수만큼 반복하여
printf("%d\n", i); // 해당 숫자를 출력
}
}
}
return 0;
}