본문 바로가기
알고리즘/programmers

42628: 이중우선순위큐

by cjw.git 2021. 3. 24.

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@gmail.com

'알고리즘 > programmers' 카테고리의 다른 글

68936: 쿼드압축 후 개수 세기  (0) 2021.04.02
72410: 신규 아이디 추천  (0) 2021.03.24
64062: 징검다리 건너기  (0) 2021.01.25
60059: 자물쇠와 열쇠  (0) 2021.01.25
43164: 여행경로[DFS/BFS]  (0) 2021.01.14

댓글