[프로그래머스][LV.3] 이중우선순위큐 | python3

문제링크:  이중우선순위큐

---

문제설명

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

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

제한조건

- operations는 길이가 1 이상 1,000,000 이하인 문자열 배열입니다.
- operations의 원소는 큐가 수행할 연산을 나타냅니다.
  - 원소는 “명령어 데이터” 형식으로 주어집니다.- 최댓값/최솟값을 삭제하는 연산에서 최댓값/최솟값이 둘 이상인 경우, 하나만 삭제합니다.
- 빈 큐에 데이터를 삭제하라는 연산이 주어질 경우, 해당 연산은 무시합니다.

---

 

문제풀이

최소힙을 이용하여 품.

최소힙이기 때문에 heappop을 하면 최솟값이 나오지만 최댓값은 정렬해서 마지막 원소를 꺼내줘야함.

 

그리고 삭제는 원소가 있을때만 수행해야 오류가 안나기때문에 조건문으로 원소가 있을때만 수행하도록 해줘야함

나의코드

import heapq as hq

def solution(operations):
    answer = []
    heap=[]
    for o in operations:
        s,n = o.split()
        
        if s=='I':
            hq.heappush(heap,int(n))
        else:
            if heap: # 원소가 있을때만 수행해야함 
                if n=='1': 
                    heap.sort() # 최댓값을 빼기 위해 정렬.
                    heap.pop()
                else:
                    hq.heappop(heap)
                    
    if heap: # 원소가 있을때 
        heap.sort() # 힙 정렬은 리스트 정렬과는 다르기 때문에 따로 정렬해줘야함
        return [heap[-1],heap[0]]
    else:
        return [0,0]
    
    return answer

 

---

 

참고하기