[programmers] 이중우선순위큐

코딩 테스트 연습 - 힙 (Heap)

---

<이중우선순위큐>

문제 설명

 

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

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

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

 

 

제한 사항

 

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

 

 

문제 풀이

 

- my solution

import heapq

def solution(operations):
    result = []
    
    for i in operations:
        x = i.split()

        if x[0] == "I": # 숫자 삽입
            heapq.heappush(result, int(x[1]))
        elif x[0] == "D":
            if x[1] == "-1": # 최솟값 삭제
                if len(result)!=0:
                    heapq.heappop(result)
            else: # 최댓값 삭제
                temp = []
                for j in result: # 최대 힙 만들기
                    heapq.heappush(temp, -int(j))
                if len(temp) != 0: # 비어있지 않으면 삭제
                    heapq.heappop(temp)
                result = []
                for j in temp: # 원래대로
                    heapq.heappush(result, -j)
        
    answer=[]
    if len(result) == 0: #큐가 비어있으면
        answer = [0, 0]
    else: # 비어있지 않으면
        k = heapq.heappop(result) # 최솟값
        temp = []
        for j in result: # 최대 힙
            heapq.heappush(temp, -j)
        answer.append(-heapq.heappop(temp)) # 최댓값
        answer.append(k) # 최솟값
            
    return answer

 

1) split을 통하여 분리하여 명령어가 I 일 때, D 일 때를 구분하여 구현

---

생각🤔

 

Level 3이었지만 크게 어렵지 않았던 문제였다. 레벨이 높아 문제 클릭하기 어려웠을 뿐...

최근에 heapq에 대하여 문제를 풀어봤던 것이 크게 도움이 되었다.

위에서 코드 설명이 짧았던 것도, heapq만 알면 쉽게 풀 수 있을 거라 생각했기 때문이다.

 

내가 생각하기에 이 문제의 포인트는

1) heapq 사용

2) 최소 힙, 최대 힙 

인 것 같다. 다행히도 최소 힙, 최대 힙을 구현할 줄 알기에 빨리 해결할 수 있었다.

 

하지만, 살짝 의문점이 드는 것은, '최소 힙이 구현된 상태에서 최대 힙을 구현할 때

모든 원소의 값을 가져와 최대 힙으로 다시 구현하는 방법밖에 없는가?'였다.

조금 더 공부해봐야겠다😥

 

문제를 풀면서 얻은 것

1. heapq

2. 최대 힙, 최소 힙

 

---

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges