파이썬으로 계수 정렬 사용해보기

https://gt40766.tistory.com/23

13. 정렬 알고리즘 : 문제 풀이 전략

위의 계수 정렬 항목 잠조

특정한 조건이 부합한다면 매우 빠른 알고리즘, 기수 정렬과 더불어 가장 빠르다.

사용하는 방법을 아래 문제를 통해 알아보자.

 

실습

10989번: 수 정렬하기 3

import sys
input = sys.stdin.readline
print = sys.stdout.write # 안 바꿔도 됌, 바꾸면 속도 증가

arr_idx = [0]*10001 # 값을 담을 리스트 생성

for i in range(int(input())): # 입력 받는 횟수를 입력 받음
    arr_idx[int(input())] += 1 # 인덱스에 입력을 받음 7을 입력 받으면 arr_idx [7] =+ 1
for i in range(len(arr_idx)):
    for j in range(arr_idx[i]): # +해준 만큼 출력
        print("%s\n"%i) # print를 안 바꿀 경우 그냥 print(i) 해주면 됨

이 문제는 입력과 출력이 많은 문제이기 때문에 sys 모듈의 함수를 불러와주었다.

이 문제에서 정렬해야하는 값의 범위가 0~ 10000이기 때문에 계수 정렬이 적절하다.

위 코드에서 print 부분만큼은 바꾸지 않고 써도 된다.