백준 10989 수 정렬하기 3

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

실패 이유 : 메모리 초과

import sys

n = int(sys.stdin.readline())
num_list = [0] * 10001

for _ in range(n):
    num_list[int(sys.stdin.readline())] += 1

for i in range(10001):				# 카운팅 정렬 사용
    if num_list[i] != 0:
        for j in range(num_list[i]):
            print(i)

• 데이터의 범위가 작은 경우 카운팅 정렬을 사용할 수 있다.
  • 데이터 범위와 크기가 같은 배열 준비
  • 데이터 값과 같은 배열의 위치에 1씩 더하기
  • 배열의 모든 정보에 대해 배열 위치 값을 배열 값 만큼 출력
• 카운팅 정렬의 시간복잡도는 O(n + k) 로, k 는 입력범위의 최대값을 의미한다.

출처 : https://yoonsang-it.tistory.com/49