백준 알고리즘 10989번 - 수 정렬하기 3

다른 정렬하기 문제와 다르게 입력이 최대 1천만번까지 주어진다.

일반적인 정렬 알고리즘이 최소 nlogn이므로 일반적인 정렬 알고리즘으로는 제한시간(3초)안에 계산 할 수 없다.

 

처음에는 sort 함수부터 bubble sort, quick sort, merge sort 까지 다 사용해봤지만,,, 계속 시간초과가 나오고 있었다.

이 문제에서 포인트는 주어지는 모든 수가 10000 이하라는 점이다.

배열을 사용해서 정렬하면, 공간복잡도는 조금 커지겠지만(그래봐야 10000밖에 안된다), 시간복잡도는 O(n+k)가 되므로 3초 안에 들어올 수 있다.

 

 

알고리즘

 

1. 크기가 10000인 배열을 하나 만들고 수가 입력될 때마다 해당 인덱스에 있는 값을 1씩 늘린다.

2. 인덱스가 각 숫자라고 생각할 수 있으므로 1부터 돌면서 배열에 있는 값이 0이 아니라면 그 수만큼 출력한다.

 

소스 코드

 

 

#include <iostream>
 
using namespace std;
 
int dp[10001] = { 0, };
int main() {
 
    int n;
    scanf("%d",&n);
 
    for (int i = 0; i < n; i++) {
        int a; 
        scanf("%d",&a);
        dp[a]++;
    }
 
    for (int i = 0; i < 10001; i++) {
        int count = dp[i];
        for(int j=0;j<count; j++)
            printf("%d\n", i);
    }   
    return 0;
}