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

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

 

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.

 

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

---

정렬을 이용한 문제.

..인데 시간 제한이 3초고 메모리 제한이 8MB고 입력받을 수 있는 수의 개수 범위가 [1, 10000000] 이다.

즉 다른 정렬 문제처럼 수를 모두 배열에 입력받은 뒤, STL 함수나 일반 정렬 알고리즘을 통해 정렬하는 방식으로 풀지 말라는 뜻이다.

 

대신 수의 범위가 [1, 10000]이기 때문에 1부터 10,000까지의 인덱스를 표시할 수 있는 정수형 벡터 number를 선언하고 0으로 초기화한다. 정수를 입력받으면 해당 인덱스에 몇 번이나 그 수가 들어왔는지 세고, 카운트 된 만큼 출력을 해주는 방식으로 풀면 된다.

 

코드

#include <cstdio>
#include <vector>

using namespace std;

int main(void) {
    int n;
    scanf("%d", &n);
    vector<int> number(10001, 0);

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

    for(int i = 1; i <= 10000; i++) {
        if(number[i] == 0) continue;
        for(int j = 0; j < number[i]; j++) {
            printf("%d\n", i);
        }
    }
    return 0;
}