[11004]K번째 수 (병합 정렬 풀이)

11004번: K번째 수

 

분석

N(1 ≤ N ≤ 5,000,000)로 nlogn 병합 정렬로 풀이

시간복잡도, 시간제한, 빅오(Big-O) 표기법

 

 

내장함수 풀이

import sys
input=sys.stdin.readline
n,k=map(int,input().split())
a=list(map(int,input().split()))

a.sort()
print(a[k-1])

 

병합정렬 풀이

import sys
input=sys.stdin.readline
n,k=map(int,input().split())
a=list(map(int,input().split()))
tmp=[0]*n  # 정렬용 임시 리스트

# 병합정렬
def mergeSort(s,e):
    if e-s<1:return
    m=int(s+(e-s)/2)  # 중간점
    # 재귀함수 형태로 표현
    mergeSort(s,m)
    mergeSort(m+1,e)

    for i in range(s,e+1):
        tmp[i]=a[i]

    # 정렬할 a리스트 인덱스
    j=s
    # 투 포인터
    idx1=s
    idx2=m+1
    # 두 그룹을 병합
    while idx1<=m and idx2<=e:
        if tmp[idx1]>tmp[idx2]:
            a[j]=tmp[idx2]
            j+=1
            idx2+=1
        else:
            a[j]=tmp[idx1]
            j+=1
            idx1+=1
    # 한쪽 그룹이 모두 선택된 후 남아있는 값 정리
    while idx1<=m:
        a[j]=tmp[idx1]
        j+=1
        idx1+=1
    while idx2 <= m:
        a[j] = tmp[idx2]
        j+=1
        idx2+=1

mergeSort(0,n-1)

print(a[k-1])