[코딩테스트] 프로그래머스 - 이중우선순위큐 (Lv.3) in Python

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

 

연산의 종류는

1. "I 숫자": 숫자를 삽입

2. "D 1": 큐에서  최댓값 삭제 

3. "D -1": 큐에서  최솟값 삭제 

 

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

 

풀이

- 어차피 숫자를 하나씩 넣으니까, 새로운 숫자를 넣을 때마다 대소관계 비교하면서 넣으면 되겠다는 생각을 했다.

- "I 숫자"연산 위해서는 bisect (이진탐색) 이용.

  : 대소관계 비교를 매 번 수행해야 하는데, 이 때 이진탐색을 이용하면 O(log n)복잡도를 띄며 효율적이기 때문이다.

   (vs. linear search of O(n))

- "D 1"과 "D -1"연산 위해서는 deque 구성.

  : deque는 pop()과 popleft() 모두 O(1)이니 효율적이기 때문이다.

   (vs. pop(0) in list of  O(n))

 

코드 구현

 

from collections import deque
from bisect import bisect_left, insort_left

def solution(operations):
    queue = deque()
    for e in operations:
        if e[0] == 'I':
            num = int(e.split(' ')[1])
            index = bisect_left(queue, num)
            queue.insert(index, num)
        elif e == 'D 1':
            if queue:
                queue.pop()
        elif e == 'D -1':
            if queue:
                queue.popleft()      
    if queue:
        answer = [queue.pop(),queue.popleft()]
    else:
        answer = [0,0]
 
    return answer

- "I 숫자"에서  split 후, int()처리를 해주지 않아 숫자 부분이 문자열로 받아들여져 정렬이 이상하게 됐다. int()처리 후 제대로 실행되었다.