[WEEK01/DAY04] 백준 문제 : 수 정렬하기 3

https://www.acmicpc.net/problem/10989

10989번: 수 정렬하기 3

이번 문제는 문제의 제한사항을 잘 확인해야 하는 문제였다.

 

파이썬에서는 길이가 1억(100,000,000)인 리스트를 사용할 때, 약 381MB의 메모리를 사용한다고 한다.

이 문제에 주어진 제한사항을 보면,

시간 제한 5초에 메모리 제한이 8MB 이다.

그러므로 최악의 상황인 천만 개의 수가 주어진다고 할 때, 이들을 정렬하기 위해 배열에 저장하면 메모리 초과가 나게 된다.

 

그래서 다른 방법을 찾아보았다.

문제의 조건을 보면 '주어지는 수는 10,000보다 작거나 같은 자연수'라는 대목이 있다.

 

나는 이에 주목하여 도수정렬 알고리즘을 활용하고자 했다.

 

도수정렬(Counting Sort)이란 원소의 대소 관계를 판단하지 않고 빠르게 정렬하는 알고리즘으로, 분포수 세기(Distribution Counting) 정렬이라고도 한다.

특징은 다음과 같다.

  - if문과 같은 비교 연산을 하지 않고도 반복문만으로 데이터를 정렬할 수 있다.

  - 데이터의 범위를 알아야 사용이 가능하다. (ex. 1 <= n <= 10000 인 자연수)

 

도수 분포표에 대한 내용은 다음 글을 참조하자.

https://mathbang.net/69

도수분포표, 변량, 계급, 계급값, 도수

 

다시 알고리즘으로 돌아가보자면, 도수분포를 구현하는 방식은

데이터 범위 크기의 리스트를 만들어서 그 리스트의 인덱스 값을 이용하는 것이다.

예를 들어 도수분포 리스트의 인덱스[5]의 값이 3이라면, 5라는 값을 가진 데이터가 3개 있다는 말이 된다.

 

	[0]	[1]	[2]	[3]	[4]	[5]	[6]	[7]
dataList (1<=n<=5인 자연수)	5	2	3	1	4	3	4	1

위 표와 같은 데이터 리스트가 있다면, 이를 도수분포표에 넣으면

	[0]	[1]	[2]	[3]	[4]	[5]
dosuList	0	2	1	2	2	1

이렇게 들어가는 것이다.

 

이 도수리스트를 이용하여, 단순히 반복문만 사용해도 우리는 정렬된 값을 얻을 수 있다.

(단, 값이 같은 데이터들끼리는 순서가 바뀌므로 안정된 정렬은 아니다.)

 

 

이 방법으로 푼 코드를 아래에 공유한다.

import sys

n = int(sys.stdin.readline().strip())

dosuArr = [0] * 10001   # 도수 분포표의 길이 == 데이터의 범위 최대값 + 1

for i in range(n):
    inputVal = int(sys.stdin.readline().strip())
    dosuArr[inputVal] += 1

for i in range(len(dosuArr)):
    for j in range(0, dosuArr[i]):
        print(i)