사용자 도구

사이트 도구


ps:problems:programmers:42748

K번째수

ps
링크https://programmers.co.kr/learn/courses/30/lessons/42748
출처프로그래머스
문제 번호42748
문제명K번째수
레벨Level 1
분류

구간 쿼리

시간복잡도Optimal: O((n+k)logn), 구현: O(knlogn)
인풋사이즈n<=100
사용한 언어Python
해결날짜2021/05/28
태그

고득점 Kit - 정렬

풀이

  • 정확히 따지면 구간 쿼리 문제. 그중에서도 구간 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]

토론

댓글을 입력하세요:
I T U H F
 
ps/problems/programmers/42748.txt · 마지막으로 수정됨: 2021/05/28 04:49 저자 teferi