프로그래머스 - 이중우선순위큐 (Heap) [Python]

 

 문제

 

programmers.co.kr/learn/courses/30/lessons/42628

코딩테스트 연습 - 이중우선순위큐

 

 

 

 

 

 

 문제 상황

 

- operations를 순회하며 명령어가 "I 숫자" 이면 큐에 숫자를 삽입하고, "D 1"은 큐에서 최댓값을 삭제하며 "D -1"은 큐에서 최소값을 삭제한다.

 

 

 

 

 

 

 해결 전략

 

- 문제는 파이썬에는 최소힙만 구현이 되어있고 최대힙이 구현되어있지 않다. 즉, 최소값을 삭제하는 것은 O(1)로 가능하지만 최대값은 그럴 수 없다. 그래서 python의 heapq의 내장함수인 nlargest를 활용한다.

 

 

 

 

 

 

 코드

 

def solution(operations:list) -> list:
    import heapq
    heap = []
    for operation in operations:
        if operation[0] == "I":
            heapq.heappush(heap, int(operation[2:]))
        elif heap:
            if operation[2] == "1":
                heap.pop(heap.index(heapq.nlargest(1, heap)[0]))
            else:
                heapq.heappop(heap)
    return [heap.pop(heap.index(heapq.nlargest(1,heap)[0])), heapq.heappop(heap)] if heap else [0,0]

 

 

 

 

 

 

 

 

 해설

 

- 조건에 따라 I인 경우 insert를 실행시키고, 조건이 I 혹은 D이므로 else이지만 여기에 heap이 비어있지 않다는 조건이 필요하므로 elif로 처리하였다. 최대값을 제거할 경우와 최소값을 제거하는 경우를 나누어 구현했다. heapq의 nlargest는 parameter로 들어오는 int값, 예를 들어 3이라면 상위 3개의 요소를 리스트로 반환한다. 반환값이 리스트이므로 뒤에 [0]을 붙여주었다. 그 값을 heap에서 인덱스로 검사하여 그 인덱스를 기준으로 pop으로 제거한다.

 

 

 

 

 

 

 

 새로 학습한 것 & 실수 

 

1. heap에서 요소를 삭제할 때 : heapq.pop(heap 이름) -> 일반 리스트의 pop()이 습관화되어 pop안에 힙 이름을 적지 않는 실수가 발생했다.

 

2. heapq.nlargest/heapq.nsmallest(int, heap 이름) : heapq의 요소중 가장 큰/작은 순서로 int개의 요소를 리스트로 반환한다. -> 1개를 뽑을 때(1,heap)으로 해도 요소가 하나가 나오는 것이 아니라 한개의 element를 가진 리스트로 반환되므로 인덱스를 해주어야한다. 

 

- 3레벨의 난이도이지만 난이도 자체가 높은 것보다 파이썬 내장 heapq를 사용할 줄 알면 쉬운 문제였다.