✨ 문제 설명

입출력 예 1

입출력 예 2

구현 아이디어

• 큐에서 최댓값과 최솟값을 계산하여 삭제해야 하기 때문에 우선순위 큐를 사용한다. (heapq 모듈 사용)
• 파이썬의 heapq는 기본적으로 최소 힙이다 → D -1에는 heappop()을 사용
• 리스트를 heapify하고 원소를 삽입하면 리스트가 정렬된다
  • 그러면, 마지막 원소는 최댓값이므로 최댓값을 계산해줄 필요 없이 마지막 원소를 pop하면 된다 → D 1에는 리스트 기본 함수 pop()을 사용

전체 코드 - 틀렸습니다

from heapq import heappush, heappop

def solution(operations):
    answer = []
    hq = []
    
    for operation in operations:
        alphabet, number = operation.split()
        number = int(number)
        if alphabet == 'I': # 주어진 숫자를 삽입
            heappush(hq, number)    
        else: # alphabet == 'D'
            if hq: # 빈 큐에서 데이터를 삭제하라는 연산이 주어졌을 시 무시
                if number == -1:
                    heappop(hq) # 최솟값을 삭제
                else:
                    hq.pop() # 최댓값을 삭제
                    
    # 모든 연산을 처리한 후     
    if hq:
        answer = [hq[-1], hq[0]]
    else:
        answer = [0, 0]
        
    return answer

전체 코드 - 정답입니다

질문 게시판을 통해 반례를 찾을 수 있었다.
최종 답을 출력할 때, hq 리스트가 정렬되지 않은 것이 원인이었다.

모든 연산을 마친 후 최소 힙의 모습은 아래와 같다.

힙은 🌲이진 트리🌲고, 우리가 사용하는 리스트는 트리를 1차원 형태로 표현한 것이다.

heap[k] <= heap[2*k+1] and heap[k] <= heap[2*k+2]

💥 힙은 정렬된 리스트가 아니라는 것을 주의하자 !! 💥

from heapq import heapify, heappush, heappop

def solution(operations):
    answer = []
    hq = []
    
    for operation in operations:
        alphabet, number = operation.split()
        number = int(number)

        if alphabet == 'I':
            heappush(hq, number)    
        else: # alphabet == 'D'
            if hq: # 빈 큐에서 데이터를 삭제하라는 연산이 주어졌을 시 무시
                if number == -1:
                    heappop(hq) # 최솟값을 삭제
                else:
                    hq.sort()
                    hq.pop() # 최댓값을 삭제
                    
    # 모든 연산을 처리한 후
    hq.sort()
    if hq: # 큐가 비어있지 않음
        answer = [hq[-1], hq[0]]
    else: # 큐가 비어있음
        answer = [0, 0]
        
    return answer

최댓값을 출력하기 전과 최종 결과를 출력하기 전에, hq 리스트를 정렬하는 코드를 추가하여 문제를 해결할 수 있었다.

heapq 시간복잡도