테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.

====== K번째수 ======

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

===== 코드 =====
<dkpr py>
"""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]
</dkpr>

{{tag>프로그래머스 ps:problems:programmers:Level_1}}