계수 정렬(Counting Sort)이란
- 특정 숫자가 얼마나 등장하는지를 카운팅 하여 출력함으로써 정렬되는 알고리즘
- 원소가 양의 정수로만 이루어져 있을 때 사용이 가능하다.
- 시간복잡도는 O(NlogN)
- 정렬하고자 하는 원소들이 특정 사이즈보다 작을 때
코드로 표현하기
- 특정 범위를 가지는 저장공간(리스트, 딕셔너리 등)을 할당한다.
- for문을 돌며 주어진 범위를 조회한다.
- 조회하면서 원소가 인덱스 i(딕셔너리라면 키)라면, list_i 를 1씩 증가시킨다.
- 각 리스트에 저장된 값만큼 i를 반복출력함으로써 정렬을 완료한다.
아래는 백준의 10889-수 정렬하기3 문제를 카운팅소트로 구현한 코드이다.
제일 먼저 떠올랐던 아이디어는 딕셔너리의 키값에 대한 카운팅 값을 value값에 저장하여 정렬하는 방법이었다. 하지만 아래 코드는 메모리초과로 실패하였다..
#딕셔너리로 구현
#결과: 메모리 초과
n = int(input())
num = {}
#1부터 n까지의 키값을 가지는 딕셔너리
for i in range(1, n+1):
num[i] = 0
for i in range(n):
now = int(input())
num[now] = num.get(now) + 1 #입력받은 값을 키값으로 가지는 항목에 1 증가시키기
for key in num.keys():
size = num.get(key)
for j in range(size):
print(key)
#리스트로 구현
#결과 : python3, pypy3로 제출했을 경우 메모리 초과
n = int(input())
count = [0 for i in range(n+1)]
#print(count)
for j in range(n):
now = int(input())
count[now] += 1
for j in range(n+1):
while count[j] > 0:
print(j)
count[j] -= 1
이 문제는 효율성을 따져봐야 해서 시행착오가 더 있었던 것 같다.
구글링을 해봤을 때 메모리 초과가 나오는 경우 해볼 수 있는 시도는 다음과 같다.
- sys모듈을 통한 입출력 받기
- 배열의 크기를 +1하여 10001로 만들어둔 후 조회하기
#통과한 코드
#추가한 것: sys.stdin.readline(), sys.stdout.write(), range(10001)
import sys
n = int(input())
count = [0 for i in range(10001)]
for i in range(n):
now = int(sys.stdin.readline())
count[now] += 1
for i in range(10001):
if count[i] > 0:
for j in range(count[i]):
sys.stdout.write(str(i)+'\n')