[BOJ-10989] 수 정렬하기 3 (Python)

🤒 문제

BOJ-10989 수 정렬하기3

💊 풀이

실패한 소스코드 (quick sort)

import sys

def quick_sort(arr: list, start: int, end: int):
    part2 = partition(arr, start, end)

    # 왼쪽
    if 1 < part2 - start:
        quick_sort(arr, start, part2 - 1)
    # 오른쪽
    if part2 < end:
        quick_sort(arr, part2, end)

def partition(arr: list, start: int, end: int):
    pivot = arr[(start + end) // 2]
    while start <= end:
        while arr[start] < pivot: start += 1
        while arr[end] > pivot: end -= 1
        if start <= end:
            arr[start], arr[end] = arr[end], arr[start]
            start += 1
            end -= 1
    return start

N = int(input())
arr = [int(sys.stdin.readline().strip()) for x in range(N)]
quick_sort(arr, 0, len(arr) - 1)
for x in arr: sys.stdout.write(str(x) + "\n")

메모리초과

퀵소트로 풀었더니 계속 메모리 초과가 났다.

보면, 메모리 제한이 8MB 이다.
int를 받으니까 int 하나는 $4 byte = 32bit$ 이고, 이걸 리스트로 만들었고, N의 갯수가 $1 ≤ N ≤ 10,000,000$ 이므로
리스트를 하나만 만들어도 $32bit ≤ 리스트크기 ≤ 320,000,000bit$가 되는데,,

그렇게 되면 이미 38MB를 넘어선다 🤦‍♀️

해결 (Counting sort)

그래서 아예 입력을 리스트나 다른 자료형으로 받으면 안된다.
1. 이 수는 10,000보다 작거나 같은 자연수이다. 라는 조건이 있으므로 길이가 10001인 리스트를 만든다.
2. 10000이 아니라 10001인 이유는 인덱스가 0부터 시작하고, 문제는 자연수만 받기 때문에 1을 받으면 인덱스가 1인 값을 증가시키기 위함이다.
3. num을 입력 받고 arr[num]를 1 증가시킨다. 계속 그것을 반복하면 그 수의 갯수만큼 증가하게 된다.
4. for문을 돌며 해당 인덱스값을 리스트[인덱스] 개 만큼 출력시킨다.

✨ 소스코드

import sys

N = int(sys.stdin.readline())
arr = [0 for _ in range(10001)]

for _ in range(N):
    num = int(sys.stdin.readline())
    arr[num] += 1

for i in range(len(arr)):
    for _ in range(arr[i]):
        print(i)

참고로 pypy3로 제출하면 여전히 메모리 초과이다. 공간적인 면에선 pypy3보다 python3가 효율이 더 좋다.