[프로그래머스/파이썬] K번째수 _ 풀이

문제

https://school.programmers.co.kr/learn/courses/30/lessons/42748

프로그래머스

 

---

 

풀이

def quick(arr, left, right):
    if left < right:
        pivot_index = partition(arr, left, right)
        # pivot보다 작은 부분
        quick(arr, left, pivot_index - 1)
        # pivot보다 큰 부분
        quick(arr, pivot_index + 1, right)

def partition(arr, left, right):
    pivot = arr[right]	# 피봇은 맨 끝으로 설정
    # i = 피봇보다 큰 수로 할당됨 = 정렬 대상
    i = left - 1
    
    for j in range(left, right):
        if arr[j] <= pivot:	# 피봇보다 작을 경우에만 정렬
            i += 1
            # 정렬 : arr[j]와 i를 스왑
            arr[j], arr[i] = arr[i], arr[j]
    
    # 디폴트 스왑
    # 1. 피봇보다 비교대상 arr[j]들이 모두 클 경우를 위해
    # 2. arr[j]들 중 큰수가 남아 있는 경우를 위해
    arr[i+1], arr[right] = arr[right], arr[i+1]
    return i + 1 
    
def solution(array, commands):
    answer = []
    
    for com in commands:
        temp = []
        # i~j까지 분할
        for i in range(com[0], com[1] + 1):
            # i번째는 i-1
            temp.append(array[i - 1])
        # 분할된 리스트 정렬 (퀵정렬)
        quick(temp, 0, len(temp)-1)
        # k번째 요소 answer 추가
        answer.append(temp[com[2] - 1])
    return answer

 

퀵 정렬 알고리즘을 사용해서 풀었다.