99클럽 코테 스터디 10일차 TIL (이중우선순위큐)

오늘의 학습 키워드:  힙

문제: 이중우선순위큐

https://school.programmers.co.kr/learn/courses/30/lessons/42628

프로그래머스

풀이

조건 중에 최댓값을 빼야 하는 경우에만 힙을 뒤집어주는 연산을 수행했다.

효율성이나 다른 테스트에서 그렇게까지 시간을 잡아먹는 케이스가 없다고 판단. 마지막 최대 최솟값 추출은 max, min함수를 사용했다.

from heapq import heapify, heappop, heappush
def solution(operations):
    answer = []
    h = []
    
    for o in operations:
        operation, value = o.split(" ")
        value = int(value)
        if operation == 'I':
            heappush(h,value)
        else:
            if value > 0:
                try:
                    h = [-1*i for i in h]
                    heapify(h)
                    heappop(h)
                    h = [-1*i for i in h]
                    heapify(h)
                except:
                    pass
            else:
                try:
                    heappop(h)
                except:
                    pass
    if len(h)==0:
        return [0,0]
    else:
        return [max(h),min(h)]

 

뒤집는 방법의 수행은 모든 요소에 -1을 곱하는 O(n)과 힙의 재구성인 O(n)의 시간이 걸리기 때문에

O(n)의 시간복잡도를 갖습니다.

 

회고

정리를 하다 보니 놓친 부분들을 다시 보게 되는 것 같습니다.

내일 학습할 것.

SQL, Python, 독서