[Python] 백준 10989번: 수 정렬하기 3

풀이 전략은 다음과 같습니다.

메모리 제한이 8MB로 매우 작습니다.
하지만 정렬해야 하는 수의 개수가 $1 ≼ N ≼ 10,000,000$으로 매우 많기 때문에
내장된 sorted 함수를 쓰면 메모리 초과가 뜨는 문제인데요!
이 문제처럼 메모리를 적게 사용해야 할 때는 계수 정렬을 사용하면 됩니다.

정렬해야 하는 모든 수를 리스트에 저장하면 크기가 N인 리스트가 필요한데요,
수의 범위가 10000보다 작거나 같은 자연수이기 때문에
계수 정렬을 사용하면 크기가 10000인 리스트만으로 정렬이 가능합니다.

방법은 다음과 같습니다.
숫자 n의 개수를 리스트[n-1]에 저장하면 됩니다.

import sys

N = int(sys.stdin.readline())
# 계수 정렬
l = [0 for i in range(10000)] # 크기 10000인 리스트

for _ in range(N):
    l[int(sys.stdin.readline()) - 1] += 1
for i in range(len(l)):
    for _ in range(l[i]):
        print(i + 1)

메모리를 적게 사용하는 정렬 방법인 계수 정렬을 떠올리는 것이 중요했던 문제로 보입니다.