[백준]10989. 수 정렬하기 3(카운팅 정렬)

 위 문제는 N개 만큼 입력되는 수를 오름차순으로 정렬하도록 하는 문제입니다. 게시물의 제목에서도 알 수 있듯이, 이 문제는 카운팅 정렬을 통해 해결할 수 있습니다.

 

`1. 문제 해결 방법?

 카운팅 정렬을 사용하는 경우를 정리하면 다음과 같습니다.

1) 입력되는 수의 범위가 적으며, 전부 0보다 크거나 같다

2) 중복이 허용된다(사실 허용 안되어도 가능)

 

 카운팅 정렬의 전반적인 아이디어는 다음과 같습니다.

1) 위의 문제처럼 입력되는 수의 범위가 1~10000이라면, 크기가 10001인 배열 c을 만든다.

2) 배열 c의 모든 요소에 0을 넣는다.

3) 새로운 수 tmp가 입력될 때 마다, 배열 c의 index를 i, 그 위치에 해당되는 값을 a라고 하면,

4) tmp == i 인 c[i]의 값을 +1 한다.

5) 출력시, 배열 c의 a값만큼 각각 i를 출력한다.

 

ex) 만일에 1~5까지의 수를 받는 경우,

 다음과 같다.

 

따라서 이를 활용에서 문제를 풀면 다음과 같다.

import sys

def count_sort():
    count = [0 for _ in range(10001)]
    
    n = int(input())
    for i in range(n):
        count[int(sys.stdin.readline())] += 1
    
    for idx, i in enumerate(count):
        for _ in range(i):
            sys.stdout.write(str(idx)+'\n')

if __name__ == '__main__':
    count_sort()