[백준 10989번/C언어] 수 정렬하기 3, 배열을 활용한 풀이

백준 10989번 문제를 배열을 활용하여 풀어보았습니다. 

백준 10989번: https://www.acmicpc.net/problem/10989 

10989번: 수 정렬하기 3

 

 

문제 내용은 아래와 같습니다. 

 

 

 이 문제는 아주 기본에 해당하는 정렬 문제입니다. Quick Sort나 Merge Sort, Bubble Sort 등 다양한 정렬 방법이 있지만 저는 가장 간단히 해결할 수 있는 배열을 활용한 정렬 방법을 사용했습니다. 사실 공간효율은 거의 포기한 느낌의 코드라고 보시면 됩니다....ㅎㅎ 여기서는 수의 크기가 10,000으로 작게 주어진 편이라 이 방법을 사용할 수 있었지만 사실 수가 조금만 더 커지거나 아니면 하나의 수가 나올 수 있는 횟수가 훨씬 더 커진다면 공간 효율 측면에서 상당히 비효율적인 방법이기 때문에 사용을 딱히 추천하지는 않습니다. 하지만 지금 문제에서는 수의 개수도 int 범위 내 값이고, 수의 최댓값도 10,000으로 작아서 이 방법을 사용하기 적합하다고 생각했습니다. 

  방법을 간략히만 먼저 말씀드리면, 일종의 hash table을 사용했다고 생각하시면 됩니다. 즉 우리가 입력받은, 정렬해야 하는 수가 key가 되고, 그 숫자가 몇 번 나왔는지가 value가 되는 것입니다. 따라서 코드 내에서 수의 최댓값 + 1의 크기(인덱스가 0부터 시작하기 때문에 정확히 해당하는 수를 인덱스로 사용하려면 +1을 해줘야 합니다.)를 가진 int 배열을 만들어서, 특정 수가 등장하면 그 인덱스에 저장된 정수 값 + 1을 해줘서 몇 번 나왔는지 카운트를 해주는 방식으로 받은 정보를 저장합니다. 그리고 정보를 다 받고 나서는 0부터 순회하면서 1번 이상 나온 수를 프린트해 주면서 넘어가면 자연히 정렬이 됩니다. 

 

 

 코드를 통해 더 자세히 보겠습니다. 우선 isMentioned라는 전역 변수 배열을 선언해줍니다. 이 배열은 앞서 언급한 대로 인덱스 수가 몇 번 나왔는지의 정보를 저장해 두는 역할을 합니다. 전역변수로 배열 크기를 지정해 주면서 선언을 하게 되면 자동으로 배열 내 모든 int 값이 0으로 초기화되기 때문에 이러한 특징을 이용한 것이라고 보면 됩니다. 

 그리고 메인 함수에 들어가서 문제에서 주어질 수의 개수인 N을 먼저 입력받아 N 변수에 저장하고, 이를 통해 반복문을 설정하여 정렬할 N개의 숫자들을 입력받습니다. 이 때, 입력받을 변수인 a와 함께 max 변수를 선언해 주는데, 이는 정보를 모두 입력받은 후 정렬한 수들을 출력할 때 불필요하게 배열 전체를 탐색하는 것을 막고, 입력받은 값들 중 최댓값까지만 순회하도록 하기 위함입니다.  그래서 if문 안에서 a를 입력받고, isMentioned 배열 내 a 인덱스를 가진 값을 1 증가시켜 준 후, 만약 a가 현재 저장된 max값보다 클 경우 max값을 바꿔주게 됩니다. 

 이렇게 수들을 입력받아 저장하는 과정을 마치고 나면, 0부터 저장된 max값까지를 다시 순회하면서 저장된 값만큼 해당 인덱스를 출력합니다. 이렇게 하면 자연히 정렬된 숫자들이 출력되게 됩니다. 

#include <stdio.h>

int isMentioned[10001];

int main() {
    int N;
    scanf("%d", &N);
    
    int a, max = 0;
    for (int i = 0; i < N; i++) {
        scanf("%d", &a);
        ++(isMentioned[a]);
        if (a > max) max = a;
    }
    for (int i = 0; i <= max; i++) {
        for (int j = 0; j < isMentioned[i]; j++)
            printf("%d\n", i);
    }
}