백준 알고리즘 10989번(파이썬) 계수정렬 (counting정렬)

counting정렬 백준 알고리즘 10989번 문제 바로가기

백준 10989번 문제는 counting정렬을 이용해서 수를 정렬하는 문제이다. 이 문제는 메모리 제한이 8MB로 굉장히 타이트하다. 풀이할때 출제자가 의도한 만큼의 배열만 사용해야 하는것을 의마한다. 질문글과 답변을 찾아보니 필요한 배열보다 한자리라도 더 큰 배열을 사용할 경우 메모리 초과가 뜬다고 한다. 문제를 보자.

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

문제는 정말 간단하다. 주어진 N개의 수를 오름차순으로 정렬한 후 차례로 출력하면 된다. 그런데 출제자는 계수정렬(counting정렬)을 사용하여 푸는 것을 의도 하고 있다.

계수정렬(counting정렬)이란 무엇일까?

지금까지는 정렬을 할때 다른 값들과 비교를 하여 정렬하는 비교정렬 알고리즘을 사용해왔다. 하지만 계수정렬은 비교가 한번도 이루어 지지 않고 정렬하는 알고리즘이다. 단순하게 표현하면 주어진 입력값들의 크기를 기준으로 수를 배열에 저장하여 정렬한다. 처음 접했을때는 잘 이해가 안갔는데 직접 코드를 짜는 과정에서 리스트의 인덱스를 이용하며 알고리즘을 이해했다.

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

for j in range(1, 10001):
    if li[j] >= 1:
        for k in range(li[j]):
            print(j)

배열의 형태로 리스트를 사용한다고 했을때 리스트의 인덱스값을 주어진 수로 생각하고 각 인덱스의 값에는 입력값들의 크기(반복횟수)를 저장한다고 생각한다. 그렇다면 먼저 입력값을 받을 리스트가 필요하기 때문에 li = [0] * 10001로 0이 10001개 들어간 리스트를 만들었다. 10000개가 아니라 10001개인 이유는 리스트의 인덱스는 실제 받는 입력값보다 1씩 작기때문에 N이 10000일 경우를 생각해서 이다. 그리고 입력받은 값들을 만들어 놓은 리스트의 인덱스와 연결시켜 해당 인덱스의 값들을 1씩더하며 저장한다. 이렇게 하면 추가적인 메모리를 사용하지않고 10001개의 리스트 한개만 사용하여 풀이 할 수 있다.

계수정렬의 시간 복잡도는 O(N) 혹은 O(N + k)라고 한다. O(N +k)가 무슨 뜻이냐면 계수정렬은 가장 큰 수의 영향을 받는다. 예를 들어 주어진 수가 (1, 2, 3, 1000)이라면 필요한 리스트의 크기는 1부터 1000까지 인덱스를 모두 가지고 있어야 하기때문에 4 ~ 999까지 불필요한 연산을 하게 되고 k가 N보다 훨씬 크다면 k의 영향이 더 크기 때문에 오히려 다른 정렬 알고리즘 보다 시간 복잡도의 값이 더 커질 수 있다.