백준 10989( 수 정렬하기3 )

백준 10989( 수 정렬하기3 ) - 파이썬(Python)

쿄코코 2022. 5. 16. 22:57

계수 정렬로 풀기

정렬 - 계수 정렬

계수 정렬 (Count Sort) : 특정한 조건이 부합할 때만 사용할 수 있지만, 매우 빠른 알고리즘( 일반적으로 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효과적으로 사용할 수

coooco.tistory.com

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

for i in range(1,len(array),1):
	# if를 하지 않을 경우 시간 초과가 난다.
    if array[i]!=0:
        for j in range(array[i]):
            print(i)

if를 선언하여 array[i]이 0이 아닐 경우에만 사용한다