백준 10989 파이썬(계수정렬)

계수정렬(counting sort)을 사용해서 풀어야하는 문제다.

 

계수정렬의 가장 큰 특징은 비교정렬이 아니다 라는 점이다.

비교정렬은 두수의 대소관계를 반복적으로 계산하면서 푸는 정렬방법인데

계수정렬은 이런 방법을 사용하는게 아니라 말 그대로 숫자들의 개수를 세면서 정렬한다.

 

그리고 계수정렬의 시간복잡도는 선형시간이다 O(n)

성능이 좋다는 다른 정렬방법(퀵정렬 - O(n^2), 병합정렬 - O(nlogn), 힙정렬 - O(nlogn))들 보다도 훨씬 빠르다.

 

그러나 단점은 제한이 많다는 것이다.

값들간의 차이 크기가 별로 없거나

값들이 정수로만 이루어져있을때 사용이 가능하다.

 

역시나 모든 문제에서 좋은 알고리즘은 없고

그때그때마다 상황에 맞는 알고리즘을 찾아서 사용해야 한다.

 

 

계수정렬의 스탭별 자세한 과정은 아래 링크에서 확인해볼수 있다.

https://www.cs.miami.edu/home/burt/learning/Csc517.091/workbook/countingsort.html

Counting Sort

---

코드

# 10989번 - 계수 정렬
import sys
n = int(input())

# counting array 초기화하기
array = [0 for _ in range(10001)] 

# counting array에 빈도수 넣기
for _ in range(n):
    num = int(sys.stdin.readline())
    array[num] += 1

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

(참고 블로그 : https://yuuj.tistory.com/105)

사실 위 코드는 카운팅정렬의 알고리즘을 정확하게 구현하고 있지는 않는 것 같다.

원래는 counting array의 역순으로 조회하면서 output array를 만들어나가야 한다.

 

 

카운팅정렬을 구현하는 코드

#counting sort 구현
def counting_sort(array, max):
 
    #counting array 생성
    counting_array = [0]*(max+1)
 
    #counting array에 input array내 원소의 빈도수 담기
    for i in array:
        counting_array[i] += 1
 
    #counting array 업데이트.
    for i in range(max):
        counting_array[i+1] += counting_array[i]
 
    #output array 생성
    output_array = [-1]*len(array)
 
    #output array에 정렬하기(counting array를 참조)
    for i in array:
        output_array[counting_array[i] -1] = i
        counting_array[i] -= 1
    return output_array

이상하게 이 코드로 백준저지에 넣으면 메모리초과가 뜬다.