10989번: 수 정렬하기

문제

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

입력

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

출력

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

 

 

---

 

풀이

https://en.wikipedia.org/wiki/Counting_sort 를 참고하되, 수도코드대로 작성하면 메모리 오류가 발생한다. 그래서, input값을 리스트로 저장하지 않고, 10001 길이의 count list를 선언해 준 후, count[input] += 1을 해줘야 한다. 시간이 엄청 오래 걸리던데, 다른 풀이 보니까 다들 이렇게 했더라.

 

 

코드

import sys

N = int(sys.stdin.readline())
count = [0]*10001
answer = []
nums = []

for i in range(N):
    i = int(sys.stdin.readline())
    count[i] += 1

for i in range(10001):
    for _ in range(count[i]):
        print(i)