[C++] 백준 10989 수 정렬하기 3

www.acmicpc.net/problem/10989

10989번: 수 정렬하기 3

 

1. 서론

 

coding-log.tistory.com/66?category=954740

[C++] 백준 1427 소트인사이드

이 문제의 두 번째 방법을 이용하면 쉽게 풀 수 있는 문제! 

 

2. 문제 풀이

 

n개의 수가 주어졌을 때, 이 수들을 오름차순으로 정렬해서 출력하는 코드를 짜야한다. 이때 n의 범위는 1~ 100000000이며, 숫자는 10000보다 작거나 같은 자연수이다. 즉, 1~ 10000까지의 수인 것이다. 

 

안될 것 같긴 했지만 일단 벡터로 코드를 짰다가 메모리 초과가 났다. n의 범위가 억 이여서 그런지 당연한 일이긴 했다.

그러다가 갑자기 소트인사이드에서 썼던 방법이 생각났다. 

숫자가 입력되면 해당 Index를 가진 배열의 값을 + 1 해주는 것이다. 그럼 그 숫자가 몇 번 나왔는지가 배열에 저장된다. 이 숫자의 범위는 1~ 10000까지이기 때문에 메모리 초과가 날 일이 없다. 그렇게 n개의 수가 전부 입력되고 나면 오름차순으로 입력된 값을 출력하면 된다.

 

이렇게 푸는 방법을 계수정렬이라 하며 수의 범위가 작을 때만 사용할 수 있다고 한다. (이 문제의 경우 수의 범위가 1~10000)

 

3. 코드 설명

 

#include <cstdio>

using namespace std;

int main()
{
    int n, i, j, t;
    int a[10001];

    for (i = 0; i < 10001; i++)
        a[i] = 0;

    scanf("%d", &n);

    for (i = 0; i < n; i++)
    {
        scanf("%d", &t);
        a[t]++;
    }

    for (i = 0; i < 10001; i++)
        for (j = 0; j < a[i]; j++)
            if(a[i] != 0)
                printf("%d\n", i);
}

 

자연수를 담을 배열을 0으로 초기화 한다.

그리고 n을 입력받은 후, 배열에 숫자의 수만큼 count 한다.

그리고 순서대로 count 한 만큼 반복해서 출력하면 된다.

 

주의할 점은 자연수의 범위이다. 깜빡하고 그냥 10000이라고 적었는데 10000 값도 포함해야 하기 때문에 10001까지로 바꿔서 적었다.

그리고 억 개의 케이스가 있기 때문에 시간 초과를 막기 위해서 scanf, printf를 사용했다.