백준 정렬 10989번

안녕하세요, GDSC 웹 멤버 오정인입니다.
파이썬 스터디의 다섯번째 문제를 풀어봤습니다.

메모리 초과

처음 문제를 봤을때 sort()를 이용하면 풀리지 않을까 생각했는데, 메모리 초과가 나왔습니다.
정렬 알고리즘이 문제인가 생각해 아는 방법을 모두 시도해 보았으나 전부 메모리 초과가 나왔습니다…
10989번의 메모리 제한은 8MB로, 모든 입력을 배열에 저장하는 방식으로는 풀 수 없었습니다.

계수 정렬(Counting Sort) 알고리즘

해당 문제를 해결할 방법으로 계수 정렬 알고리즘을 사용했습니다.

  • 계수 정렬 알고리즘은 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을때만 사용할 수 있습니다.
  • 배열의 인덱스를 특정한 데이터의 값으로 여기며,각 숫자가 나온 빈도를 계산해 정렬하는 방식입니다.
  • 선택 정렬, 삽입 정렬, 퀵 정렬 등과 같은 비교 기반의 정렬 알고리즘이 아닙니다.
  • 계수정렬의 시간복잡도는 O(n+k)이며 k는 배열에서 등장하는 최댓값입니다.


계수 정렬은 정렬할 수들의 최대값에 영향을 받기 때문에 k가 n보다 작다는 것이 보장된 경우 O(n)의 효율적인 시간복잡도를 가지지만,k가 n보다 클 경우 비효율적이라고 합니다.

코드

입력을 받을 때 input( )보다는 stdin.readline( ) 을 이용하는 것이 훨씬 빠르다고 하여 이를 사용하였습니다. 

import sys
n=int(sys.stdin.readline())
lst=[0 for i in range(10001)]
#리스트 값을 선언, 전부 0으로 초기화
for i in range(n):
    lst[int(sys.stdin.readline())]+=1
#리스트의 인덱스로 값을 표현하는 방법을 사용
for i in range(10001):
    if lst[i]>0:#해당 인덱스에서의 값이 0보다 클 경우
        for _ in range(lst[i]):#그 값만큼 인덱스를 출력합니다
            print(i)

마무리

계수 정렬 알고리즘을 새롭게 알게 되었습니다!사용해서 풀 때를 잘 구분하면 좋을 것 같습니다.


참고자료

https://h-sseung.tistory.com/m/50?category=961404
https://h-sseung.tistory.com/m/50?category=961404