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

import sys
input = sys.stdin.readline

n = int(input())

count_array = [0]*(10001)

for i in range(n):
  data = int(input())
  count_array[data] += 1

for i in range(len(count_array)):
  for j in range(count_array[i]):
    sys.stdout.write(str(i)+'\n')

이번 문제는 앞서 풀었던 수 정렬하기 시리즈 1,2 와는 다르게 공간 복잡도(메모리 제한)을 고려해야 하는 문제이다.

 

첫번째로 pypy3를 기준으로 input()이 아닌 sys.stdin.readline() 을 사용하였고, 두번째로 print()가 아닌 sys.stdout.write()을 사용하였다.

 

하지만 가장 중요한 점은 이 문제의 조건이 수의 개수가 10,000,000개까지 주어질 수 있기 때문에 단순히 파이썬 정렬 라이브러리(sort, sorted)를 사용하거나, n개의 입력을 모두 저장하게 된다면 시간초과 or 메모리초과를 맞게 될 것이다.

 

따라서 시간 복잡도 O(N+K)를 보장하는 계수 정렬(Count Sort)를 사용하여 문제를 해결하였다 :)