수 정렬하기 3

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

예제 입력 1

10
5
2
3
1
4
2
3
5
1
7

예제 출력 1

1
1
2
2
3
3
4
5
5
7

코드

오류 코드

import sys

N = int(sys.stdin.readline())
N_list = []

for i in range(N):
	N_list.append(int(sys.stdin.readline()))
   
N_list.sort()
for i in range(N):
	print(i)

이렇게 하면 메모리 초과로 실패하게 됩니다.
입력받는 것도 sys를 사용해서 그나마 좋게 했다고 생각했는데, 메모리 초과가 뜨니깐 당황스러웠습니다.

해결 코드

import sys

N = int(sys.stdin.readline())

N_list = [0]*10001

for _ in range(N):
    n = int(sys.stdin.readline())
    N_list[n] += 1
    
for i in range(10001):
    if N_list[i] != 0:
        for j in range(N_list[i]):
            print(i)

알고보니 입력받는 수의 범위와 관련되어 있었습니다.
첫째 줄에 받는 수의 범위가 심각하게 넓었던 것이 었습니다. append()를 for문에서 사용하면 계속 재할당되다보니 메모리 초과가 발생하는 것입니다.
그래서 둘째 줄부터 입력받는 수의 범위에 맞게 따로 배열을 만들었습니다.
여기서 딱 맞게 10000개로 만들게 되면 런타임에러가 발생합니다.
왜인지는 아직 모르겠지만, 배열 크기는 데이터 범위를 포함시켜서 할당해야 하는 것 같습니다.