[BOJ] 10989번: 수 정렬하기3 | Python

About Algorithm

문제

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

입력

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

출력

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

풀이

처음으로 메모리 에러가 뜬 문제. 지금까지는 항상 입력을 다 저장하고 봤는데, 그러면 안 된다는 것을 깨닫게 해준 문제였다.

'이 수는 10,000보다 작거나 같은 자연수이다' 문장이 힌트였다. 자연수의 범위가 1부터 10,000까지로 한정되어 있으므로, 배열의 크기를 10,000로 하여, 입력을 받을 때마다 해당 자리에 그 수가 입력된 횟수를 하나씩 늘리면 된다. 나는 배열의 크기를 10,001로 하여, 해당 수를 그 배열의 인덱스로 둘 수 있게끔 했다. 예를 들어, 1이 입력되면 array[0]이 아니라 array[1]에 +1 하는 식이다.

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

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

for idx in range(1,10001):
  for _ in range(nums[idx]):
      sys.stdout.write(str(idx)+'\n')