파이썬/백준 문제
[파이썬][백준] 11004번: k번째 수
코딩고치
2020. 5. 31. 18:07
1. 문제
주소: https://www.acmicpc.net/problem/11004
11004번: K번째 수
수 N개 A1, A2, ..., AN이 주어진다. A를 오름차순 정렬했을 때, 앞에서부터 K번째 있는 수를 구하는 프로그램을 작성하시오.
www.acmicpc.net
문제 유형: 정렬
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])