[백준 문제풀이] 2751 - 수 정렬하기 2

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

문제

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

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

출력

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

풀이

2024년 1월 기준으로 정답 비율이 31%여서 그 정도로 어려운 문젠가? 하고 풀었는데 나 역시 틀려버렸다..

틀려버린 이유들은

1. 시간 초과 (퀵 정렬인데 시간 초과가 걸려서 input, output을 sys함수를 이용해서 다시 짬)
2. 런타임에러(Recursion Error) 재귀함수의 깊이가 너무 깊어지면 생기는 에러라고 하는데, 내가 구현한 QuickSort()함수가 재귀함수라 생기는 에러인듯했다.

틀린 코드

import sys

input = sys.stdin.readline
print = sys.stdout.write

N = int(input().rstrip())

arr = []
for _ in range(N):
    arr.append(int(input()))


def QuickSort(arr):
    if len(arr) <= 1:
        return arr

    p = arr[int(len(arr) / 2)]
    arr1, arr2, arr3 = [], [], []

    for num in arr:
        if num > p:
            arr3.append(num)
        elif num < p:
            arr1.append(num)
        else:
            arr2.append(num)

    return QuickSort(arr1) + arr2 + QuickSort(arr3)


arr = QuickSort(arr)
for i in range(len(arr)):
    print("".join(str(arr[i])) + "\n")

정답 코드

import sys

input = sys.stdin.readline
print = sys.stdout.write

N = int(input().rstrip())

arr = []
for _ in range(N):
    arr.append(int(input()))

arr.sort()
for i in range(len(arr)):
    print("".join(str(arr[i])) + "\n")

기본 내장 함수인 sort()함수로 힘겹게? 통과했다.

기본 내장 함수의 sort()가 궁금하다면 https://github.com/python/cpython/blob/main/Objects/listobject.c#L2577 를 참고해보자.