[Python] 백준 10989번: 수 정렬하기 3 - 카운팅 정렬 (Counting Sort)

문제

10989번: 수 정렬하기 3

풀이

그동안 수 정렬하기 문제가 있을때는 간편하게 파이썬의 sorted()를 사용했지만,

이 문제는 메모리 제한이 있어서 카운팅 소트를 사용해서 풀어야 한다. 

 

카운팅소트(Counting Sort)란

https://yuuj.tistory.com/106

[정렬] 계수 정렬 (카운팅소트, Counting Sort)

원소끼리 비교를 하지 않고 원소가 몇번 등장하는지 갯수를 세서 정렬하는 방법이다. 따라서 퀵정렬, 병합정렬에 비해 일반적으로 빠르다.

 

1. 각 숫자의 빈도를 저장하기 위한 배열 생성

2. 각 숫자에 해당하는 인덱스에 빈도수 저장 (따라서 리스트의 모든 원소는 양의 정수여야 한다)

3. 배열을 탐색하며 저장된 빈도수만큼 인덱스 출력

하는 방식으로 풀었다.

 

 

시간복잡도는 O(n+k)으로 굉장히 빠르지만, 만약 정렬해야하는 리스트가 [0, 1, 9999]일때는 배열에 2부터 9998까지 불필요한 공간을 만들어야하기 때문에 비효율적이다. 같은 맥락에서 n의 값이 너무 커지면 일반 정렬 알고리즘보다 느려질 수 있는 단점이 있다.

정렬을 위한 길이 n의 배열 하나, 계수를 위한 길이 k의 배열 하나. O(n+k) 의 공간복잡도를 가진다.

 

 

코드

import sys

# counting sort에서 빈도 저장하기 위한 배열
li = [0 for _ in range(10001)]

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

# 인풋으로 받은 수가 몇변 들어왔는지 빈도 저장
for _ in range(N):
    num = int(sys.stdin.readline())
    li[num] += 1

# 배열의 시작부터 돌며 저장된 빈도만큼 인덱스값을 출력
for i in range(1, 10001):
    count = li[i]
    for _ in range(count):
        print(i)

 

참고한 포스팅

https://yaboong.github.io/algorithms/2018/03/20/counting-sort/

https://dojinkimm.github.io/algorithm/2019/09/22/sort-algorithm-8.html