[백준] 2751 수 정렬하기 2 Python

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

 

📝  문제

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

 

🔎  풀이

퀵 소트를 구현해서 풀었다. 퀵 소트를 만들 때 피벗을 항상 중앙에 있는 인덱스로 두고 풀었는데, 시간 초과가 나서 랜덤으로 바꿨더니 해결할 수 있었다.

 

💻  코드

import sys
import random

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    
    pivot = arr[random.randrange(0, len(arr))]
    lesser_arr, equal_arr, greater_arr = [], [], []

    for num in arr:
        if num < pivot:
            lesser_arr.append(num)
        elif num > pivot:
            greater_arr.append(num)
        else:
            equal_arr.append(num)
    
    return quick_sort(lesser_arr) + equal_arr + quick_sort(greater_arr)

numbers = []
for i in range(int(sys.stdin.readline().strip())):
    numbers.append(int(sys.stdin.readline().strip()))

numbers = quick_sort(numbers)
for i in numbers:
    sys.stdout.write(str(i) + '\n')