42628: 이중우선순위큐

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

---

1. 문제

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

  I 숫자	큐에 주어진 숫자를 삽입합니다.
  D 1	큐에서 최댓값을 삭제합니다.
  D -1	큐에서 최솟값을 삭제합니다.

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

 

---

2. 문제의 조건

• 1 <= operations <= 1000000
• 삭제할 연산이 없을경우 삭제연산은 무시

 

---

3. 문제 접근

• 아이디어
  
  문제 종류가 heap으로 되어있습니다. 자료구조를 이용하여 풀면 쉽게 풀 수 있는 문제입니다.

 

---

4. 풀이 방법

• 명령어와 수치로 나눕니다.
• 만약 추가명령이라면 heapq의 heappush를 이용해 값을 추가합니다. O(log N)
• 만약 삭제연산이라면 heap의 길이가 0보다 큰지 판단 후 크다면 삭제해줍니다.
  이 때, 최대값의 삭제는 list의 pop으로 처리해줍니다 O(1)
  최소값의 삭제는 heapq.heappop(heap)으로 해줍니다 O(log N)
• 만약 heap의 크기가 0보다 크다면 heap의 최대값과 최소값을 리턴하고, 0이라면 [0, 0]을 리턴합니다.

 

---

5. 소스코드

• cjw-git.tistory.com/152

 

---

 

cjw.git@gmail.com