[알고리즘 문제풀이] K 번째 수

문제 제목 : K 번째 수

문제 난이도 : 중

문제 유형 : 정렬

https://www.acmicpc.net/problem/11004
시간 제한 : 2초
메모리 제한 : 512MB

문제풀이 아이디어

1. 데이터 최대 5,000,000개 -> (병합, 퀵, 힙 등)정렬을 이용해야 한다.
   -> 시간 복잡도 O(N logN)의 정렬 알고리즘
2. python의 기본 정렬 라이브러리를 사용해도 문제를 풀 수 있다.
3. 시간적인 이점을 위해서 pypy3를 선택하여 코드를 제출하는 것이 좋다.

< 소스코드 >

# Merge Sort -> Dived & conquer
def merge_sort(array):
    if len(array) <= 1:
        return array
    mid = len(array) // 2
    left = merge_sort(array[:mid])
    right = merge_sort(array[mid:])
    i, j, k = 0, 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            array[k] = left[i]
            i += 1
        else:
            array[k] = right[j]
            j += 1
        k += 1
    if i == len(left):
        while j < len(right):
            array[k] = right[j]
            j += 1
            k += 1
    elif j == len(right):
        while i < len(left):
            array[k] = left[i]
            i += 1
            k += 1
    return array

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

array = merge_sort(array)

print(array[k-1])

# python 기본 라이브러리 이용
n, k = map(int, input().split())
array = list(map(int, input().split()))

array = sorted(array)

print(array[k-1])