[구현] (2-2) 자료구조의 원하는 구간만 sorting하기

문제 :  K번째 수

N개의 숫자로 이루어진 숫자열이 주어지면 해당 숫자열중에서 s번째부터 e번째 까지의 수를 오름 차순 정렬했을 때 k번째로 나타나는 숫자를 출력하는 프로그램을 작성하세요.

<입력설명>
첫 번째 줄에 테스트 케이스 T(1<=T<=10)이 주어집니다.
각 케이스별
첫 번째 줄은 자연수 N(5<=N<=500), s, e, k가 차례로 주어진다. 두 번째 줄에 N개의 숫자가 차례로 주어진다.

<출력설명>
각 케이스별 k번째 수를 아래 출력예제와 같이 출력하세요.

입력예제

2
6253 527389 15 3 10 3

4 15 8 16 6 6 17 3 10 11 18 7 14 7 15

출력예제

 

#1 7
#2 6

입력예제1 해설 :
case 1 : 2 7 3 8의 숫자 중 오름차순 정렬 했을 때 3번째 숫자는 7이다.
case 2 : 8 16 6 6 17 3 10 11의 숫자 중 오름차순 정렬 했을 때 3번째 숫자는 6이다.

 

파이썬 언어에서는 어떠한 배열(list)의 원하는 부분을 가져오는것이 쉽다

 

list[start_index : while_end_index]
list[start_index : end_index+1 : jump]

 

for문의 문법과 비슷

start_index 부터 시작해서 while_end_index가 나올때까지 반복하겠다!

즉 만약 원하는 end_index까지를 포함시키려면 end_index+1 이면 된다.

 

import sys
input = sys.stdin.readline

def find(s, e, k, num_list):
    part_list = sorted(num_list[s - 1:e])
    # print(part_list)
    return part_list[k-1]

T = int(input())
res_list = []
for i in range(T):
    N, s, e, k = map(int, input().split())
    num_list = list(map(int, input().split()))
    res = find(s, e, k, num_list)
    res_list.append(f"#{i+1} {find(s, e, k, num_list)}")

for res in res_list:
    print(res)