K번째수

• 정확히 따지면 구간 쿼리 문제. 그중에서도 구간 k-th 쿼리문제이다.
• 일반적인 경우에서는 Persistent Segment Tree나 Merge Sort Tree 등을 사용해서, 쿼리당 O(logn) 또는 O(log^2(n))에 처리하는 것을 목표로 해야 한다. BOJ의 K번째 수 문제가 그런경우로, n이 최대 10만으로 주어진다.
• 그러나 이 문제는 n이 겨우 최대 100이라서, 그냥 무식하게 매 쿼리마다 구간을 진짜로 정렬해보는 방식으로 풀어도 충분하다. 쿼리당 O(nlogn)이지만 n이 작아서 이게 실제로도 더 빨리 동작할수도 있다. 매 쿼리마다 구간에 대해서 O(n)의 선택 알고리즘 을 쓰는 것도 마찬가지 이유로 불필요.
• 이 방식으로 푼다면 총 시간복잡도는 O(knlogn).
• 머지소트 트리를 이용해서 O(nlogn + klog^2(n))에 푸는 코드가 필요하다면 K번째 수 을 참고.

"""Solution code for "Programmers 42748. K번째수".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/42748
- Solution link: http://www.teferi.net/ps/problems/programmers/42748
"""


def solution(array, commands):
    return [sorted(array[i - 1:j])[k - 1] for i, j, k in commands]