코드업(codeup) 3014 : 정렬을 빠르게! C언어

▶문제 : 정렬을 빠르게! (codeup.kr)

정렬을 빠르게!

 

▶코드 작성(밑에 개선 코드)

#include <stdio.h>
#define N 100000//최대 숫자

int arr[N];

int main()
{
    int n, temp;

    scanf("%d", &n);

    for (int i = 0; i < n; i++)
    {
        scanf("%d", &temp);
        arr[temp]++;//입력된 숫자의 배열자리를 1씩 증가시킨다.
    }

    for (int i = 0; i < N; i++)
    {
        if (arr[i] > 0)//1이상일 때
        {
            for (int j = 0; j < arr[i]; j++)//증가된 수만큼
            {
                printf("%d ", i);
            }
        }
    }

    return 0;
}

 

▶개선 코드

#include <stdio.h>
#define N 100000//최대 숫자

int arr[N];

int main()
{
    int n, temp, max = 0;

    scanf("%d", &n);

    for (int i = 0; i < n; i++)
    {
        scanf("%d", &temp);
        arr[temp]++;//입력된 숫자의 배열자리를 1씩 증가시킨다.
        if (temp > max) max = temp;//입력된 숫자의 최댓값
    }

    for (int i = 0; i <= max; i++)//최댓값만큼 반복문
    {
        if (arr[i] > 0)//1이상일 때
        {
            for (int j = 0; j < arr[i]; j++)//증가된 수만큼
            {
                printf("%d ", i);
            }
        }
    }

    return 0;
}

 

▶해석

입력되는 숫자의 최댓값을 배열의 크기로 정하여 입력된 수를 배열의 자리에서 +1씩 해주었다. 그리고 입력된 수의 최댓값을 변수 max에 구하여 다음 반복문에서 불필요한 수까지 반복하는 상황을 제거하였다. 반복문으로 i를 max까지 반복하여 배열의 i자리가 1 이상이면 i숫자가 있다는 말이므로 i를 출력하였다.