[백준 / Python] 수 정렬하기 3

수 정렬하기 3

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

코드

sort() 를 사용했더니 메모리 초과 -> 메모리 제한(8MB)

계수 정렬(counting sort) 알고리즘의 일종으로, 입력받은 정수들을 1부터 10000까지의 범위 내에서 정렬
계수 정렬은 특정 조건(정수의 범위가 한정되어 있고, 데이터의 수가 많을 때) 하에서 매우 빠른 정렬 알고리즘

import sys

input = sys.stdin.readline

n = int(input())


arr = [0] * 10000

for i in range(n):
    a = int(input()) 
    #print(a)
    arr[a-1] += 1 # 인덱스 저장 
print(arr)
for i in range(10000):
    if arr[i] != 0: # input() 저장 
        for j in range(arr[i]):
            print(i+1)