선택 문제

선택 문제

n개의 숫자들 중에서 k번째로 작은 숫자를 찾는 문제

▶ 숫자들을 정렬한 후, k번째 숫자 찾기

퀵 정렬을 수행하면서 피벗의 위치를 기준으로 k번째의 숫자를 찾을 것

 

k는 1부터 배열의 길이까지 선택 가능

인덱스는 0부터 시작하므로 내가 3번째 위치의 수를 찾고자한다면 인덱스로는 2에 위치한 수를 출력하면 됨

k = 피벗인덱스 + 1 일 때 피벗의 값을 출력하면 됨(피벗[인덱스])

ex) k = 3 이면 피벗인덱스가 2일 때 그 값을 출력

 

import random

# 퀵정렬을 수행하며 k번째 작은 숫자 찾기
# 피벗의 인덱스 + 1 이 k면 피벗 출력
def selection_k_min(arr, k):
    if 0 < k and k <= len(arr):

        stack = [(0, len(arr)-1)]     # 검색 범위 저장
        while stack:
            findRange = stack.pop()
            start = findRange[0]
            end = findRange[1]
            
            if (start > end):
                continue

            pivot = arr[start]
            pidx = start
            for j in range(start+1, end+1):
                if arr[j] < pivot:
                    pidx += 1
                    arr[pidx], arr[j] = arr[j], arr[pidx]

            arr[start], arr[pidx] = arr[pidx], arr[start]

            if k == pidx + 1:
                print(arr)
                return arr[pidx]
            if k <= pidx:
                stack.append((start, pidx-1))
            else:
                stack.append((pidx+1, end))


# 출력
if __name__ == "__main__":
    a = [random.randrange(1, 1000) for i in range(10)]
    print("== Data ==")
    print(a)

    k = 3
    n = selection_k_min(a, k)
    
    print(k, "번째 값 : ", n)

 

실행 결과