백준 10989번 수 정렬하기 3

백준 알고리즘

10989 수 정렬하기 3

문제 설명을 보면

카운팅 정렬 방식을 사용하라고 나와 있다.

카운팅 정렬 방식은 숫자가 나온 횟수를 이용하여 정렬하는 방식이다.

아래는 파이썬으로 직접 작성한 카운팅 정렬 방식이다.

# counting sort

lst=[]
n=int(input())
for i in range(n):
    lst.append(int(input()))
num_dict=dict(zip(set(lst),[0]*len(set(lst))))
for item in lst:
    num_dict[item]+=1
for item in num_dict.keys():
    if item!=list(num_dict.keys())[0]:
        num_dict[item]=num_dict[item]+num_dict[tmp]
    tmp=item

lst_sort=[0]*len(lst)
for i in range(len(lst)-1,-1,-1):
    lst_sort[num_dict[lst[i]]-1]=lst[i]
    num_dict[lst[i]]-=1
for item in lst_sort:
    print(item)

이 방식을 통해 실행하면 메모리 초과가 발생한다.

코드를 비효율적으로 작성하긴 했다 ㅜ.ㅜ

카운팅 정렬의 기본 개념만을 이용해서 간결하게 코드를 작성할 수 있다.

아래는 새로 수정한 코드이다.

# counting sort
import sys
lst=[0]*10001
n=int(input())
for i in range(n):
    x=int(sys.stdin.readline())
    lst[x]+=1
for i in range(10001):
    if lst[i]!=0:
        for j in range(lst[i]):
            print(i)

입력에서 발생하는 오버헤드를 줄이기 위해 sys 라이브러리의 표준 입력을 사용했다.

정렬된 수를 리스트에 다시 삽입하여 리스트를 출력하는 부분이 효율성이 떨어진다.

이 부분을 단순히 카운트 된 수만큼 해당 숫자를 출력하는 방식으로 줄였다.

10989 수 정렬하기 3

추가적으로 카운팅 정렬을 애니메이션화 한 설명 링크를 아래에 업로드했다.

이해하는 데 큰 도움이 되기 때문에 참고하면 좋을 것 같다.

카운팅 정렬