Coding Test/Sort
[11004]K번째 수 (병합 정렬 풀이)
Karla Ko
2023. 6. 6. 11:36
728x90
11004번: K번째 수
수 N개 A1, A2, ..., AN이 주어진다. A를 오름차순 정렬했을 때, 앞에서부터 K번째 있는 수를 구하는 프로그램을 작성하시오.
www.acmicpc.net
분석
N(1 ≤ N ≤ 5,000,000)로 nlogn 병합 정렬로 풀이
시간복잡도, 시간제한, 빅오(Big-O) 표기법
1초 제한 n으로 구성된 O( )를 계산했을 때의 값이 1억 정도면 1초 정도의 시간이 걸린다고 한다. 예를 들어 N의 최대값이 10만이라고 문제에서 주어진다면 1. O(N) 의 시간복잡도일 경우에 값이 10만
karla.tistory.com
내장함수 풀이
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])
728x90