알고리즘 수업 - 병합 정렬 1

• 그냥 푸는것은 주어진 머지소트의 수도코드를 모두 구현해서 그대로 시뮬레이션을 돌리면서 k번째로 저장되는 수를 체크하기만 하면 된다. 시간복잡도는 머지소트를 돌리다가 k번째에서 멈추므로, O(min(k, nlogn))이 된다
• 하지만, k번째로 저장되는 수를 찾기 위해서, 머지소팅을 전부 할 필요는 없다. a[p..q]와 a[q+1..r]을 머지하면 r-a+1 번 저장하게 된다는 것은 머지를 안하고도 바로 계산할수 있다. 이런식으로 어떤 구간을 머지할때 몇번의 저장횟수가 소모되는지만 체크하면, 최종적으로 k번째의 저장이 어느 구간에서 일어나는지 알수 있다. 그러면, 그 구간만 소팅해서 그 구간에서의 k번째 수를 출력하면 끝. 결국은 최종적으로 찾은 구간을 소팅해야 하므로 시간복잡도는 여전히 O(nlogn)이지만, 직접 구현한 머지소트대신 빌트인 sort를 해당 구간에 한번만 적용하면 되므로 더 빠르게 동작한다.
• 사이즈가 n인 구간을 머지소트 할때 몇번의 저장이 필요한지 계산하는 것도, 시뮬레이션을 안돌리고도 그냥 계산할수 있는 방법이 있지 않을까 싶긴 한데.. (간단히 생각해서 n이 2^k라면 값을 바로 구할수 있는것처럼) 거기까지는 잘 안떠올라서 패스..

"""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()