백준_10989_수 정렬하기3(정렬)

from sys import stdin
from heapq import heappop, heappush

n = int(input())
n_list = []

for _ in range(n):
    heappush(n_list, int(stdin.readline().rstrip()))

for i in range(n):
    print(heappop(n_list))

당당하게 힙 정렬을 통해 풀었지만 메모리 초과가 났다.
조건의 메모리가 입력 전부를 리스트로 받기에는 너무 작았다.

N의 최대 갯수보다 N의 최대 크기가 더 작으므로 리스트를 숫자에 대한 리스트로 만들고 그 숫자에 대해 몇 개가 입력되었는지를 저장한다. 이렇게하면 나중에 다시 정렬할 필요도 없다.

from sys import stdin

S = 10001
n = int(input())
n_list = [0] * S

for _ in range(n):
    i =int(stdin.readline().rstrip())
    n_list[i] += 1

for i in range(S):
    for j in range(n_list[i]):
        print(i)

스스로 풀진 못했지만 숫자의 최대 값이 입력 수보다 적으면 이런식으로도 정렬할 수 있다는 것을 배웠다.