프로그래머스. 이중우선순위큐 파이썬 풀이

프로그래머스. Level 3. 이중우선순위큐 파이썬 풀이

문제링크 https://programmers.co.kr/learn/courses/30/lessons/42628

힙에 대한 문제인데 힙을 사용해서 풀 수도 있고, 사용하지 않아도 풀 수 있다.

힙 사용 X 풀이

def solution(operations):
    
    array = []
    
    for s in operations:
        command = s.split()
        
        if 'I' in command[0]:
            array.append(int(command[1]))
            array.sort()
        elif 'D' in command[0] and command[1] == '1':
            if array:
                array.pop(-1)
            else:
                continue
        elif 'D' in command[0] and command[1] == '-1':
            if array:
                array.pop(0)
            else:
                continue
    
    return [array[-1], array[0]] if array else [0,0]

nlargest와 heapify를 사용하여 힙을 하나만 사용할수도 있다

import heapq

def solution(operations):
    
    heap = []
    
    for s in operations:
        command = s.split()
        
        if 'I' in command[0]:
            heapq.heappush(heap, int(command[1]))
        elif 'D' in command[0] and command[1] == '1':
            if heap:
                heap = heapq.nlargest(len(heap), heap)[1:]
                heapq.heapify(heap)
            else:
                continue
        elif 'D' in command[0] and command[1] == '-1':
            if heap:
                heapq.heappop(heap)
            else:
                continue
    
    return [heapq.nlargest(1, heap)[0], heapq.heappop(heap)] if heap else [0,0]

heap을 두 개 사용하는 풀이

import heapq

def solution(operations):
    
    min_heap = []
    max_heap = []
    
    for s in operations:
        command = s.split()
        
        if 'I' in command[0]:
            heapq.heappush(min_heap, int(command[1]))
            heapq.heappush(max_heap, (-1*int(command[1]), int(command[1])))
        elif 'D' in command[0] and command[1] == '1':
            if min_heap and max_heap:
                maxi = heapq.heappop(max_heap)[1]
                min_heap.remove(maxi)
            else:
                continue
        elif 'D' in command[0] and command[1] == '-1':
            if min_heap and max_heap:
                mini = heapq.heappop(min_heap)
                max_heap.remove((mini*-1, mini))
            else:
                continue
    
    if min_heap and max_heap:
        return [heapq.heappop(max_heap)[1], heapq.heappop(min_heap)]
    else:
        return [0,0]