[파이썬][백준] 11004번: k번째 수

1. 문제

주소: https://www.acmicpc.net/problem/11004

11004번: K번째 수

문제 유형: 정렬

2. 소스코드

• Quick Slection으로 정렬하지 않고 바로 k번째 수를 찾으려 하였으나 메모리 초과

def q_selection(num_list, k):
    pivot = num_list[0]
    left, right, mid = [], [], []
    for num in num_list:
        if num < pivot:
            left.append(num)
        elif num > pivot:
            right.append(num)
        else:
            mid.append(num)

    if k < len(left):
        return q_selection(left, k)
    elif k < len(left) + 1:
        return mid[0]
    else:
        k = k - len(left) - len(mid)
        return q_selection(right, k)


n, k = map(int, input().split(' '))
n_list = list(map(int, input().split(' ')))

print(q_selection(n_list, k - 1))

• 병합 정렬을 이용하여 pypy3로 다시 제출 (python 3으로 제출할 경우 시간 초과)

def mergesplit(num_list):
    if len(num_list) <= 1:
        return num_list

    mid = len(num_list) // 2
    left = mergesplit(num_list[:mid])
    right = mergesplit(num_list[mid:])
    return merge(left, right)


def merge(left, right):
    result = []
    left_index, right_index = 0, 0

    while len(left) > left_index and len(right) > right_index:
        if left[left_index] > right[right_index]:
            result.append(right[right_index])
            right_index += 1
        else:
            result.append(left[left_index])
            left_index += 1
    while len(left) > left_index:
        result.append(left[left_index])
        left_index += 1
    while len(right) > right_index:
        result.append(right[right_index])
        right_index += 1
    return result


n, k= map(int, input().split(' '))
n_list = list(map(int, input().split(' ')))

sorted_list = mergesplit(n_list)

print(sorted_list[k - 1])