ps | |
---|---|
링크 | acmicpc.net/… |
출처 | BOJ |
문제 번호 | 24060 |
문제명 | 알고리즘 수업 - 병합 정렬 1 |
레벨 | 실버 4 |
분류 |
분할정복 |
시간복잡도 | O(nlogn) |
인풋사이즈 | n<=500,000 |
사용한 언어 | Python |
제출기록 | 89468KB / 416ms |
최고기록 | 416ms |
해결날짜 | 2022/09/19 |
"""Solution code for "BOJ 24060. 알고리즘 수업 - 병합 정렬 1".
- Problem link: https://www.acmicpc.net/problem/24060
- Solution link: http://www.teferi.net/ps/problems/boj/24060
"""
def solve(n, k, nums):
def solve_rec(beg, l):
if l <= 1:
return None
half_len = (l + 1) // 2
if (ret := solve_rec(beg, half_len)) is not None:
return ret
if (ret := solve_rec(beg + half_len, l - half_len)) is not None:
return ret
nonlocal k
if k <= l:
return sorted(nums[beg:beg + l])[k - 1]
else:
k -= l
return None
return solve_rec(0, n)
def main():
N, K = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
answer = solve(N, K, A)
print('-1' if answer is None else answer)
if __name__ == '__main__':
main()