[백준 / BOJ] - 10989번 수 정렬하기 3 C++ 풀이

---

 

백준 - 단계별로 풀어보기 [10989] 

https://www.acmicpc.net/problem/10989

문제

 

 

풀이

 

수의 개수의 최댓값이 10,000,000이기 때문에 시간 제한 2초를 만족시키기가 어렵다.

이 때, 문제에서 주어진 조건에 입력되는 수는 반드시 10000보다 작거나 같다고 하였으므로, 배열 전체를 정렬하기보다는

1부터 10000까지의 숫자가 각각 몇번 나오는지를 체크하고, 각 숫자를 횟수만큼 1부터 10000까지 순서대로 출력해주는 방식을 사용하기로 하였다.

 

코드

 

#include <cstdio>
#include <vector>
using namespace std;
int main() {
    int num,tmp;
    int count[10001] = {0,};
    scanf("%d",&num);

    for(int i = 0; i < num; i++)
    {
        scanf("%d",&tmp);
        count[tmp]++;
    }

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

 

평가

 

주어진 수의 개수는 많은데, 입력받는 숫자의 경우의 수는 10000개밖에 안된다는 사실을 활용하여 시간을 단축시키는 것이 관건인 문제이다.