K번째 수 - Python, heap

 

 

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

프로그래머스

 

 

 

풀이 - 나의 생각

기존에 자바로 풀었을 때는 정렬을 사용해서 풀었는데

 

Heap을 사용하니 정렬이 필요 없었다.

 

최솟값, k번째 작은 값, k번째 큰 값 등 다양하게 활용이 가능하다.

 

---

1. 최솟값

 

import heapq

min_heap = [3, 1, 4, 1, 5, 9, 2]
heapq.heapify(min_heap) # 리스트를 최소 힙으로 변환

min_value = min_heap[0]
print(min_value) # 출력 : 1

 

혹시 원본 리스트를 보존하고 싶다면

 

import heapq

original_list = [3, 1, 4, 1, 5, 9, 2]
min_heap = original_list[:] # min_heap = original_list 로 하면 안 됨
heapq.heapify(min_heap)  # 리스트를 최소 힙으로 변환

# 최솟값 확인
min_value = min_heap[0]
print(min_value)  # 출력: 1

---

2. k번째 작은 값

 

import heapq

numbers = [7, 10, 4, 3, 20, 15]
k = 3 # 찾고자 하는 순번

heapq.heapify(numbers)
kth_smallest = [heapq.heappop() for _ range(k)][-1]
print(kth_smallest) # 출력 : 7

 

 

---

3. k번째 큰 값

 

import heapq

numbers = [7, 10, 4, 3, 20, 15]
k = 3

heaqp.heapify(numbers)
kth_largest = heapq.nlargest(k, numbers)[-1]
print(kth_largest) # 출력 : 10

 

 

[-1]의 의미는 반환된 리스트에서 마지막 요소를 뜻하는 것입니다.

 

 

코드

 

import heapq

def solution(array, commands):
    answer = []
    
    for i in commands:
        heap = array[i[0]-1:i[1]]
        heapq.heapify(heap)
        answer.append([heapq.heappop(heap) for _ in range(i[2])][-1])
        
    return answer

 

 

 

 

 

 

 

다음에 또 봐요