백준 10989번(수 배열하기 3)

📒 알고 가야 하는 것

계수 정렬(Counting Sort) 알고리즘
- 수가 몇 번이 나오는지 횟수를 세고 해당 index에 저장하고 출력하는 방식
- Sort처럼 보이지만 Sort가 아닌 느낌(?) 참으로 획기적인 것 같다.

📌 코드

import sys

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

for i in range(N) :
    tmp = int(sys.stdin.readline())
    num_list[tmp] += 1

for i in range(1, len(num_list)) :
    for j in range(num_list[i]) :
        print(i)

📌 피드백

- 계수 정렬 알고리즘에 대해 전혀 알지 못했고 감조차 오지 않았다.
- 나중에 다시 볼 필요가 있는 문제이며 자원을 아낄 수 있는 알고리즘이다.