[백준] 10989. 수 정렬하기3

문제

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

입력

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

출력

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

제출

import sys
input = sys.stdin.readline

n = int(input())

# 10,000보다 작거나 같은 자연수
q = [0] * 10001

for i in range(n):
    q[int(input())] += 1

for i in range(1, 10001):
    if q[i] != 0:
        for j in range(q[i]):
            print(i)

문제 풀이

1년 전에 풀다가 못 풀었던 문제를 재도전했다.

메모리 초과와 시간 초과의 늪에서 허우적허우적거리다가

이 분의 블로그를 보고 풀 수 있었다.

일단 주목해야할 점은 아래와 같이 메모리 제한이 작다.

먼저 리스트에 무작정 숫자를 추가해서 정렬하는 방식으로 하게 되면 메모리 제한에 걸리게 된다. 따라서 이와 같은 방식으로 풀면 안된다.

입력으로 들어오는 숫자가 1부터 10000로 범위가 한정되어 있기 때문에 Counting Sort(계수 정렬)를 쓰기에 적합하다.

Counting Sort에 대해 정리해놓은 블로그에 따르면 Counting Sort는 입력 범위가 한정되어 있는 경우에 쓰기 적합하다고 한다.

(리스트의 공간을 미리 초기화시키면 메모리 초과가 나지 않는다고 한다.)

그리고 입력으로 들어오는 값을 index로 해서 리스트의 값을 하나씩 높이는 것이다.

그래서 5가 입력으로 들어오면 리스트[5] += 1 와 같은 절차를 진행하는 것이다.

런타임 에러

런타임 에러는 보시다시피 IndexError인데 값이 10000까지 들어갈 수 있는데, 아래와 같이 리스트를 할당해서 그랬다.

q = [0] * 10000

아래와 같이 할당해야 1부터 10000까지 0으로 할당할 수 있다.

q = [0] * 10001

pypy3 vs python3

pypy3는 메모리 초과로 틀렸는데, python3는 맞았습니다!가 떴다.

pypy3가 메모리를 더 차지하는 것 같다. 다음에 한번 이 부분에 대해 알아봐야겠다.

참고 사이트

1. Counting Sort : 계수 정렬
2. [Python] 백준 알고리즘 #10989 수 정렬하기 3
3. [BaeKJoon] 10989번: 수정렬하기 3 (Python)