[백준] 10989번 - 수 정렬하기 3 (정렬) - 결과 포함

www.acmicpc.net/problem/10989

10989번: 수 정렬하기 3

이전의 수를 정렬하는 두 문제와 같이 수들을 오름차순으로 정렬하는 문제이다.

이 문제에서는 입력이 최대 10,000,000까지 주어질 수 있으나

입력할 수 있는 수의 유효 범위는 10,000까지 밖에 안된다.

 

이 입력이 의미하는 것은 중복되는 수는 많을 수 있지만 작은 범위안에서 주어진다는 것이다.

이러한 특징을 이용해 효율적으로 빠르게 정렬할 수 있는 정렬 알고리즘은 계수 정렬이다.

 

계수 정렬은 한정된 범위안에서 주어지는 정수인 숫자들을 정렬하는데 탁월한 성능을 가지고 있다.

계수 정렬은 O(n + K)까지 성능이 나올 수 있기 때문에 정렬 알고리즘들 중에서 거의 가장 빠른것으로 알려져 있다.

 

입력될 수 있는 1 ~ 10000을 배열로 미리 선언해놓고 입력을 받을 때마다

그 숫자에 해당 하는 인덱스를 갖는 배열 값의 카운트를 증가시킨다.

 

마지막에 출력할때는 카운트를 셌던 배열을 보면서 들어있는 값만큼 해당 인덱스를 출력해주면 된다.

 

[소스 코드]

import sys

n = int(sys.stdin.readline().rstrip())

count = [0] * 10001
for _ in range(n):
    num = int(sys.stdin.readline().rstrip())
    count[num] += 1

for i in range(len(count)):
    for j in range(count[i]):
        print(i)