[프로그래머스][python]더 맵게_시간초과_heapq

최혜원·2022년 8월 19일
0

관련 문제

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

😥Problem: 시간초과(효율성)

Why?

  • 초반에 우선순위 큐가 python 에는 없는 줄 알고 from collections import deque를 활용했었다.
  • 그러나 이렇게 되면 정렬을 하고 insert를 하는 과정에서 O(n)의 시간 복잡도가 매번 발생하게 된다.

😊Solution: heapq 사용

  • python 의 PriorityQueue인 heapq를 사용했더니 해결되었다.

사용법

import heapq

#삽입
heapq.heappush(리스트, 원소)
#삭제
heapq.heappop(리스트)
#list to heapq
heapq.heapify(리스트)
#

응용: 최대 힙

  • reverse 되어 최대값을 갖는 heap을 구해보자
  • 방법 1
import heapq

heap = [1, 3, 5, 7, 9]
max_heap = [] #빈 리스트 준비
for h in heap:
	heapq.heappush(max_heap, (-h, h))
#이러면 출력이 max_heap = [(-9, 9), (-7, 7), (-5, 5), (-3, 3), (-1, 1)]
max_item = heapq.heappop(max_heap)[1] #최대값은 튜플의 두번째에 있으므로
  • 방법 2
from heapq import nsmallest #n개의 작은것들 반환
from heapq import nlargest #n개의 큰것들 반환

#각각 그중 마지막 원소가 최소, 최댓값.
nsmallest(3, [4, 1, 7, 3, 8, 5])[-1]
nlargest(3, [4, 1, 7, 3, 8, 5])[-1]
#이런식으로 사용
profile
ML_engineer

0개의 댓글