python 백준 알고리즘 10989번: 수 정렬하기 3

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

10989번: 수 정렬하기 3

 

 

카운팅 정렬(Counting Sort, 계수 정렬) - 주어진 배열의 값 범위가 작은 경우 빠른 속도를 갖는 정렬 알고리즘, 최댓값과 입력 배열의 원소 값 개수를 누적합으로 구성한 배열로 정렬을 수행한다.

 

이번에는 기존방식 사용시 메모리 초과가 뜨게 된다. 공간복잡도를 줄이는 형식으로 풀어야 하는 문제.

 

 

내 제출

import sys

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

num_list = [0] * 10001  # index가 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)