[Programmers] 정렬 - K번째 수

K번째 수 문제는 읽자마자 파이썬의 리스트 인덱싱, 슬라이싱으로 풀면 금방 풀릴 것이라고 확신했다.

먼저 commands로 받은 i번째부터 j번째까지 슬라이싱하여 새 리스트에 저장하는 방식을 택했다.

commands는 2차원 리스트 형태이므로 전체 commands의 수만큼 순회하면서 0번(i에 해당)과 1번(j에 해당) 원소를 불러와 array를 슬라이싱해 주고 해당 리스트를 새로운 리스트에 추가해 준다.

다음으로 나중에 몇 번째 숫자가 필요한지도 필요한데, 나중에 일일이 접근하기는 번거로우니 순서대로 find라는 새로운 리스트에 또 추가해준다.

def solution(array, commands):
    sorted_arr = []
    find = []
    
    for i in range(len(commands)):
        sorted_arr.append(array[commands[i][0]-1:commands[i][1]])
        find.append(commands[i][2])

 

다음으로는 오름차순 정렬이 필요한데, 파이썬에서 리스트의 정렬을 sort() 함수로 쉽게 할 수 있다.

다만, 이차원 리스트 형태이기 때문에 각 리스트 속에 있는 리스트를 불러와서 정렬을 수행해야 한다.

정렬이 끝남과 동시에 앞서 저장해뒀던 k번째 수를 인덱싱하여 정답 리스트에 추가해준다. 이때, 3번째 수는 실제 파이썬에서는 0번부터 시작하기 때문에 2인데, 인덱싱에서 이를 고려하여 find[i]-1을 해줘야 한다. 그렇지 않으면 인덱싱 범위가 벗어났다고 에러가 뜨며 실행되지 않기 때문이다.

for i in range(len(sorted_arr)):
        sorted_arr[i].sort()
        answer.append(sorted_arr[i][find[i]-1])

 

문제 설명

배열 array의 i번째 숫자부터 j번째 숫자까지 자르고 정렬했을 때, k번째에 있는 수를 구하려 합니다.

예를 들어 array가 [1, 5, 2, 6, 3, 7, 4], i = 2, j = 5, k = 3이라면 array의 2번째부터 5번째까지 자르면 [5, 2, 6, 3]입니다.

1에서 나온 배열을 정렬하면 [2, 3, 5, 6]입니다. 2에서 나온 배열의 3번째 숫자는 5입니다.

배열 array, [i, j, k]를 원소로 가진 2차원 배열 commands가 매개변수로 주어질 때, commands의 모든 원소에 대해 앞서 설명한 연산을 적용했을 때 나온 결과를 배열에 담아 return 하도록 solution 함수를 작성해주세요.

 

제한사항

array의 길이는 1 이상 100 이하입니다.

array의 각 원소는 1 이상 100 이하입니다.

commands의 길이는 1 이상 50 이하입니다.

commands의 각 원소는 길이가 3입니다.

 

입출력 예

array commands return

[1, 5, 2, 6, 3, 7, 4] [[2, 5, 3], [4, 4, 1], [1, 7, 3]] [5, 6, 3]

 

입출력 예 설명

[1, 5, 2, 6, 3, 7, 4]를 2번째부터 5번째까지 자른 후 정렬합니다. [2, 3, 5, 6]의 세 번째 숫자는 5입니다.

[1, 5, 2, 6, 3, 7, 4]를 4번째부터 4번째까지 자른 후 정렬합니다. [6]의 첫 번째 숫자는 6입니다.

[1, 5, 2, 6, 3, 7, 4]를 1번째부터 7번째까지 자릅니다. [1, 2, 3, 4, 5, 6, 7]의 세 번째 숫자는 3입니다.

 

최종 코드

def solution(array, commands):
    answer = []
    sorted_arr = []
    find = []
    
    for i in range(len(commands)):
        sorted_arr.append(array[commands[i][0]-1:commands[i][1]])
        find.append(commands[i][2])
    
    for i in range(len(sorted_arr)):
        sorted_arr[i].sort()
        answer.append(sorted_arr[i][find[i]-1])
    
    return answer