[Python/파이썬] 백준 11931번 수 정렬하기 4

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

코드

합병 정렬(Merge Sort)

import sys
input = sys.stdin.readline

n = int(input())
arr = [int(input()) for _ in range(n)]


def merge_sort(arr):
    n = len(arr)
    if n == 1:
        return arr

    left = merge_sort(arr[:n//2])
    right = merge_sort(arr[n//2:])

    l_idx, r_idx = 0, 0
    result = []
    while l_idx < len(left) and r_idx < len(right):
        if left[l_idx] > right[r_idx]:
            result.append(left[l_idx])
            l_idx += 1
        else:
            result.append(right[r_idx])
            r_idx += 1

    while l_idx < len(left):
        result.append(left[l_idx])
        l_idx += 1

    while r_idx < len(right):
        result.append(right[r_idx])
        r_idx += 1
    return result
    
print(*merge_sort(arr), sep="\n")

퀵 정렬(Quick Sort)

import sys
input = sys.stdin.readline

n = int(input())
arr = [int(input()) for _ in range(n)]


def quick_sort(arr):
    n = len(arr)
    if n <= 1:
        return arr
    pivot = arr[n//2]

    left = []
    right = []
    for i in range(n):
        if i == n//2:
            continue
        if arr[i] > pivot:
            left.append(arr[i])
        else:
            right.append(arr[i])
    return quick_sort(left)+[pivot]+quick_sort(right)
    
 
 print(*quick_sort(arr), sep="\n")

힙 정렬(Heap Sort)

import sys
input = sys.stdin.readline

n = int(input())
arr = [int(input()) for _ in range(n)]


def heapify(arr, n, root):
    smallest = root
    left_child = root*2+1
    right_child = root*2+2

    if left_child < n and arr[left_child] < arr[smallest]:
        smallest = left_child
    if right_child < n and arr[right_child] < arr[smallest]:
        smallest = right_child

    if smallest != root:
        arr[smallest], arr[root] = arr[root], arr[smallest]
        heapify(arr, n, smallest)


def heap_sort(arr):
    n = len(arr)

    for i in range(n//2-1, -1, -1):
        heapify(arr, n, i)

    for i in range(n-1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]
        heapify(arr, i, 0)
    return arr


print(*heap_sort(arr), sep="\n")

 

내장되어 있는 정렬 메서드를 사용하면 당연히 빠르고 쉽게 풀 수 있지만, 정렬 알고리즘 구현하는 방법 연습해볼 겸 해서 3가지 방법으로 풀었다. 다른 정렬 알고리즘도 있지만, 해당 문제에 주어진 N의 범위가 커서 시간 복잡도가 O(NlogN)인 방법만 사용했다.

 

그리고 빠른 정렬 알고리즘을 사용해도 입력받는 부분을 

import sys
input = sys.stdin.readline

이렇게 해주지 않으면 시간 초과가 발생한다.