[백준] #24060(합병정렬), #2751 (퀵정렬)

# 24060

5주차 학습내용 중 병합정렬 관련 문제 풀어보았다.

def mergeSort(A, p, r):
    if (p<r and count <= K):
        q = (p+r) // 2
        mergeSort(A, p, q)
        mergeSort(A, q+1, r)
        merge(A,p,q,r)
        
def merge(A, p, q, r):
    global count, result
    i = p ; j = q+1 ; t = 0
    tmp = []
    while i<=q and j<=r:
        if A[i] <= A[j]:
            tmp.append(A[i])
            i += 1
        else:
            tmp.append(A[j])
            j += 1
    
    while i<=q:
        tmp.append(A[i])
        i += 1
    while j<=r:
        tmp.append(A[j])
        j += 1
    
    i = p ; t = 0
    while i <= r:
        A[i] = tmp[t]
        count += 1
        if count == K:
            result = A[i]
            break
        t += 1
        i += 1
        
N, K = map(int, input().split())
A = list(map(int, input().split()))
count = 0
mergeSort(A, 0, N-1)
print(result)

---

#2751

결론부터 말하면 시간초과!

기본 정렬 문제를 내장함수 안 쓰고, 퀵 정렬로 풀어보기로 했다.

기존에 내장함수 사용하여 쉽게 푼 코드

import sys
n_row = int(input())
list_row=[]

for i in range(n_row):
    row = int(sys.stdin.readline())
    list_row.append(row)

list_row.sort()

for j in list_row:
    print(j)

퀵정렬 사용하여 푼 코드

import sys
input = sys.stdin.readline

def quickSort(A, p, r):
    if p<r:
        q = partition(A, p, r)
        quickSort(A, p, q-1)
        quickSort(A, q+1, r)
        
def partition(A, p, r):
    x = A[r]
    i = p-1
    for j in range(p,r):
        if A[j] < x :
            i += 1
            A[i], A[j] = A[j], A[i]
    
    A[i+1], A[r] = A[r], A[i+1]
    return i + 1

N = int(input())
lst = []

for _ in range(N):
    a = int(input())
    lst.append(a)

quickSort(lst, 0, N - 1)

for i in lst:
    print(i)

input을 sys.stdin.readline으로 바꿔도 시간초과가 나길래 왜인지 찾아봤는데,

https://www.acmicpc.net/board/view/31887

1. O(N^2)짜리 정렬 알고리즘을 사용하면 당연히 시간 초과입니다. 이에 해당하는 것으로는 버블 정렬, 선택 정렬, 삽입 정렬 등이 있습니다. 이 문제는 O(NlogN) 이하의 복잡도를 갖는 정렬을 사용해야 하고, 이에 해당하는 것으로는 병합 정렬, 힙 정렬 등이 있습니다. 또는 기수 정렬이나 카운팅 정렬을 사용해도 됩니다.
2. 퀵 정렬은 최악의 경우 O(N^2)입니다. 이름에 quick이 있다고 속으면 안 됩니다. 평균 시간복잡도는 O(NlogN)이지만, 평범하게 구현한 퀵 정렬은 매우 단순한 방법으로 최악의 케이스의 시간복잡도인 O(N^2)을 만들 수 있습니다. 단순히 이미 정렬이나 역정렬된 상태로만 입력이 주어져도 퀵 정렬이 감당할 수 없습니다.
   1) 이를 회피하는 방법으로 피벗으로 중앙값의 중앙값 고르기, 재귀가 깊어지면 다른 정렬을 사용하기, 랜덤으로 섞은 뒤에 수행하기 등이 있지만 정말 잘 구현하지 않으면 여전히 효율이 매우 안 좋습니다.
   2) 그래서 퀵 정렬은 그냥 이 문제에 사용하지 않기를 권장합니다. 이 문제 뿐만 아니라 어떤 알고리즘 문제에도 사용하지 않는 것이 좋습니다. 연습하기 위한 목적으로만 쓰세요. 이 문제에서는 수가 중복되지 않기 때문에 랜덤으로 섞기나 피벗을 가운데에 두는 것 등은 비교적 잘 되기는 하지만, 굳이 안전하고 어디서든 쓸 수 있는 방법들을 놔두고 위험한 길을 택할 필요는 없습니다. 개인적으로는 직접 구현할 거라면 병합 정렬이 가장 쉽고 디버깅하기도 용이하다고 생각합니다.

피벗을 잘 잡아야 퀵정렬이 의미가 있는데, 그걸 구현한다 하더라도 백준 문제풀이상에선 효율이 구리다는 것

연습용으로 써 본 것으로 하자.