[백준-11004] K번째 수

문제

수 N개 A1, A2, ..., AN이 주어진다. 
A를 오름차순 정렬했을 때, 앞에서부터 K번째 있는 수를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 N(1 ≤ N ≤ 5,000,000)과 K (1 ≤ K ≤ N)이 주어진다.

둘째에는 A1, A2, ..., AN이 주어진다. (-109 ≤ Ai ≤ 109)

 

출력

A를 정렬했을 때, 앞에서부터 K번째 있는 수를 출력한다.

 

정답

N, K = (map(int,input().split()))
A = list(map(int,input().split()))

def solution(N, K, A):
    answer = 0
    quicksort(0, N-1, K-1)
    answer = A[K-1]
    return answer

def quicksort(S, E, K):
    global A
    if (S < E):
        pivot = partition(S, E)
        if (pivot < K):
            quicksort(pivot+1, E, K)
        elif (K < pivot):
            quicksort(S, pivot-1,  K)
        else:
            return


def partition(S, E):
    global A

    if(S+1 == E):
        if A[S] > A[E]:
            swap(S, E)
        return E

    pivot = (S + E)//2
    swap(S, pivot)
    pivot = S
    i = S + 1
    j = E
    while(i <= j):
        while A[pivot]> A[i] and i<len(A)-1:
            i += 1
        while(A[pivot] < A[j] and j>0):
            j -= 1
        if i <= j:
            swap(i, j)
            i += 1
            j -= 1
    temp = A[pivot]
    A[S] = A[j]
    A[j] = temp
    return j



def swap(a,b):
    global A
    A[a], A[b] = A[b], A[a]


print(solution(N, K, A))