백준 10989 - 수 정렬하기 3

https://www.acmicpc.net/problem/10989

• 파이썬 시간 제한 5초, 메모리 제한 8 MB

수의 개수가 주어질 때 최때 10,000,000 주어질 수 있음
리스트에 int 원소 하나 추가할 때마다 28 + 8 (리스트 포인터)가 늘어남
따라서 10,000,000을 추가하면 메모리 제한 오류가 발생함

2~30분 고민했는데 답은 문제에 있었음
바로 수가 10,000보다 작거나 같은 자연수라는 같다는 점인데 딕셔너리의 크기를 10000으로 제한하고 value에 카운트만 하면 메모리 크기를 엄청 줄일 수 있음

import sys

n = int(sys.stdin.readline().strip())
num_list = {i: 0 for i in range(1, 10001)}
for i in range(n):
    num = int(sys.stdin.readline().strip())
    num_list[num] += 1
for i in num_list.keys():
    for i2 in range(num_list[i]):
        print(i)