[프로그래머스] 이중우선순위큐

Category	ps/자료구조
Tag	자료구조
Tags	heap
난이도	level 3
메모	heapq.nlargest
발행 여부
사이트	프로그래머스
이해	완벽히 이해
최종 편집 일시	@2021년 12월 20일 오후 7:49
푼 날짜	@2021년 12월 20일 오전 11:22

문제 해설 및 주의사항

원문

문제 설명

제한사항

입출력 예

입출력 예 설명

풀이

내 풀이 코드 (단일 heapq) (엄밀히는 틀린 답안)

풀이 코드 (heapq.nlargest 이용)

퇴고

문제 해설 및 주의사항

원문

문제 설명

이중 우선순위 큐는 다음 연산을 할 수 있는 자료구조를 말합니다.

명령어	수신 탑(높이)
I 숫자	큐에 주어진 숫자를 삽입합니다.
D 1	큐에서 최댓값을 삭제합니다.
D -1	큐에서 최솟값을 삭제합니다.

이중 우선순위 큐가 할 연산 operations가 매개변수로 주어질 때, 모든 연산을 처리한 후 큐가 비어있으면 [0,0] 비어있지 않으면 [최댓값, 최솟값]을 return 하도록 solution 함수를 구현해주세요.

제한사항

• operations는 길이가 1 이상 1,000,000 이하인 문자열 배열입니다.

• operations의 원소는 큐가 수행할 연산을 나타냅니다.
  • 원소는 “명령어 데이터” 형식으로 주어집니다.- 최댓값/최솟값을 삭제하는 연산에서 최댓값/최솟값이 둘 이상인 경우, 하나만 삭제합니다.

• 빈 큐에 데이터를 삭제하라는 연산이 주어질 경우, 해당 연산은 무시합니다.

입출력 예

operations	return
["I 16","D 1"]	[0,0]
["I 7","I 5","I -5","D -1"]	[7,5]

입출력 예 설명

16을 삽입 후 최댓값을 삭제합니다. 비어있으므로 [0,0]을 반환합니다.7,5,-5를 삽입 후 최솟값을 삭제합니다. 최대값 7, 최소값 5를 반환합니다.

---

풀이

• 최대 길이가 1,000,000 으로 매우 길다. 효율적인 문제 접근이 필요하다. 세 가지의 기능을 구현해야 한다.
  1. 삽입
  2. 최댓값 추출
  3. 최솟값 추출
  • 위의 연산들을 빠르게 할 수 있는 자료구조 heap 을 떠올릴 수 있다.
    • 하지만, 최소 힙일 때, 최댓값 추출은 어떻게 할 것인가?
    • 최소 힙이라는 자료구조에는 최댓값 추출 이라는 동작은 없지만 python 에서는 기본적으로 list 를 기반으로 최소 힙을 구현하기 때문에, 맨 마지막 index 인 heap[-1] 에 있을 것이다.
    • 최소 힙은 가장 작은 값만을 보장한다 . 나머지 값에 대한 정렬은 보장하지 않는다.
      • 그래서 아래의 처음의 풀이 코드에서 제대로 된 답이 나오지 않은 것이다.
        1. 최대 힙을 하나 더 만들기
        2. heapq.nlargest 사용하여 max 값 실제로 추출하기

내 풀이 코드 (단일 heapq) (엄밀히는 틀린 답안)

import heapq
def solution(operations):
    heap = []
    for operation in operations:
        
        action, num = operation.split(" ")
        num = int(num)
        
        if action == "I":
            heapq.heappush(heap, num)
        elif heap and action == "D":
            # 최댓값 삭제
            if num == 1:
                heap.pop()
            # 최솟값 삭제
            elif num == -1:
                heapq.heappop(heap)
                
    return [0, 0] if not heap else [heap[-1], heap[0]]

• 6번 test case 가 실패가 나온다.
  • 하지만, return [0, 0] if not heap else [max(heap), heap[0]] 으로 마지막을 수정해주면 답이 나오긴 한다.
  • 그래도 최댓값 삭제시에 heap.pop() 이 무조건 최댓값을 추출하는 것을 보장하지는 않기 때문에 엄밀히는 틀린 답이다. 프로그래머스의 테스트 케이스가 빈약한 것

💡

힙 구조는 가장 우선순위가 높은 값이 먼저 pop 되는 것을 보장하는 자료구조입니다.

pq[0]가 가장 우선순위가 높은 값(가장 작은값)인 것은 맞지만, 나머지 값에 대한 정렬은 보장하지 않는다는 의미입니다.

예를 들어

pq = []

heapq.heappush(pq, 1)

heapq.heappush(pq, 3)

heapq.heappush(pq, 5)

heapq.heappush(pq, 2)

heapq.heappush(pq, 4)

print(pq)

=> [1, 2, 5, 3, 4]

이란 결과가 나옵니다. pq[0]는 가장 작은 값이 맞지만 pq[-1]가 가장 큰 값이라는 것은 보장되지 않습니다.

풀이 코드 (heapq.nlargest 이용)

import heapq
def solution(operations):
    min_heap = []
    for operation in operations:
        
        action, num = operation.split(" ")
        num = int(num)
        
        if action == "I":
            heapq.heappush(min_heap, num)
        elif min_heap and action == "D":
            # 최댓값 삭제
            if num == 1:
                # 최소 힙에서 최댓값 제거하기
                min_heap = heapq.nlargest(len(min_heap), min_heap)[1:]
                heapq.heapify(min_heap)
                # 2번째 방법
                # min_heap.pop(min_heap.index(heapq.nlargest(1, min_heap)[0]))
                
            # 최솟값 삭제
            elif num == -1:
                heapq.heappop(min_heap)
    
    return [max(min_heap), min_heap[0]] if min_heap else [0,0]

• heapq 내장 모듈인 nlargest 를 사용할 수 있다.

---

퇴고