BOJ 10989 수 정렬하기 3

https://www.acmicpc.net/problem/10989
시간 3초, 메모리 8MB
input :

• N(1 ≤ N ≤ 10,000,000)
• 숫자 (1 <= 숫자 <= 10,000)

output :

• 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력

---

배열을 이용해서 저장하면 개수가 1천만개 까지 입력될 수 있기 때문에 메모리 초과 가 발생한다.

계수정렬을 이용하자.
그리고 더 나아가 시간을 조금 더 줄이고 싶다면 for문을 이용하지 말고 곱셈을 이용하는 것이 좋다.

import sys

n = int(sys.stdin.readline())
data = [0] * 10001
for i in range(n):
    temp = int(sys.stdin.readline())
    data[temp] += 1

for i in range(1, 10001):
    print('{0}\n'.format(i) * data[i], end="")

end="" 를 스페이스 없이 만들어서 \n 이 제대로 수행 되도록 한다.