[백준 10989] 수 정렬하기 3

문제 정보

 

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

예제

예제

---

나의 풀이

아주 간단한 문제 같아 보이지만 정답률이 23%에 그치는 것을 보면 많은 사람들이 의외의 어려움을 겪는 문제인 것이다.

가장 큰 문제는 메모리이다. 8MB 제한인데 10,000,000개의 숫자를 모두 배열이나 리스트에 담아 정렬을 하려면 40MB의 메모리는 잡아먹을 것이다.

그렇기 때문에 모든 숫자를 메모리에 담지 않고도 정렬을 할 수 있어야 한다.

나는 여기서 계수 정렬 알고리즘을 사용하였다.

계수 정렬에 대한 예제와 설명은 아래 글에서 자세히 설명해두었다.

2021.08.21 - [Python] 계수 정렬 (Count sort)

[Python] 계수 정렬 (Count sort)

 

이 문제를 계수 정렬로 푼 이유는 숫자의 범위가 10,000보다 작거나 같은 자연수이기 때문이다.

가장 큰 숫자가 10,000보다 클 수 없기 때문에 10,000개의 저장 공간만 마련하면 되는 것이다.

일반적인 방법(비교 기반 정렬)으로는 최대 10,000,000개의 데이터를 담고, 정렬하는... 엄청난 작업을 해야 했는데 그것의 1/1,000 만큼만 메모리를 사용하면서 정렬할 수 있기 때문에 계수 정렬이 이 문제에 딱 적합한 정렬 알고리즘이라고 판단했다.

그리고 여기서 또 중요한 점은 계수 정렬을 사용하더라도 python의 input() 메소드는 매우 느리기 때문에 더 빠른 방법이 필요하다.

import sys
num = int(sys.stdin.readline())

위의 소스 코드가 바로 input() 메소드보다 빠른 입력 방법이다.

(단, Jupyter Notebook에서는 동작하지 않는다. 에러를 발생시키지만 백준에 채점을 맡기면 정상적으로 처리된다.)

하나 더 보자면, 보통 빠른 실행 속도를 위해 Python3 대신 PyPy3를 많이 사용할 것이다.

그러나 pypy3는 속도가 빠른 대신 메모리 사용량이 조금 더 많다.

채점 결과

3가지 채점 결과가 있다.

가장 위에 있는 것은 계수 정렬을 사용하고, 입력을 받을 때 input() 메소드로 받은 것이다. 시간 초과가 발생했다.

두 번째에 있는 것은 계수 정렬을 사용하고, 입력을 받을 때 input() 대신 sys.stdin.readline을 사용한 것이다. PyPy3 환경에서는 메모리 초과가 발생했다.

마지막에 있는 것은 계수 정렬을 사용하고, 입력을 받을 때 input() 대신 sys.stdin.readline을 사용한 것이다. 두 번째 시도와 다르게 Python3로 채점을 했다. 이 경우 정답을 받을 수 있었다.

 

전체 소스 코드

import sys
n = int(sys.stdin.readline())
count = [0] * 10001
for _ in range(n):
    count[int(sys.stdin.readline())] += 1
for i in range(10001):
    for j in range(count[i]):
        print(i)

다시 한 번 말하지만 sys.stdin.readline()은 주피터 노트북에서는 동작하지 않는다. 하지만 백준에 채점을 해보면 정상적으로 동작한다.

주피터 노트북 환경에서 돌려보고 싶다면 sys.stdin.readline() 으로 되어있는 부분만 input()으로 변경하면 될 것이다.