10989-수 정렬하기 3 (python)

1. 계수 정렬(Counting sort): 데이터의 개수가 많은 대신 범위가 좁을 때 사용할 수 있는 정렬 알고리즘
  - 배열의 인덱스가 곧 데이터의 값이라고 생각하면 된다
  - 이제 데이터가 나올 때마다 해당 인덱스의 값을 증가시킨다 (해당 인덱스의 값 = 데이터의 개수)

2. 데이터 개수가 많을 땐 sys.stdin.readline() 함수를 사용해야 한다 (input() 함수에 비해 더 빠르기 때문)

3. PyPy3은 Python3에 비해 시간은 빠르지만 메모리를 많이 소모한다. 이 문제는 메모리 제한이 더 강하기 때문에, Python3를 이용해 제출한다

import sys

n = int(input())
nums = [0] * 10001
for _ in range(n):
    x = int(sys.stdin.readline())
    nums[x] += 1

for x in range(1, 10001):
    if nums[x] != 0:
        for c in range(nums[x]):
            print(x)