https://www.acmicpc.net/problem/7662

🥚문제

---

🥚입력/출력

---

🍳코드

import sys
import heapq
input = sys.stdin.readline

t = int(input())
for _ in range(t):
    k = int(input())

    # 최대 힙, 최소 힙을 사용하는데
    # 힙에 삽입할 때 (값, id) 형태의 튜플로 삽입하여 동기화하기 좋게 한다
    min_heap, max_heap = [], []

    # id
    id = 0

    # removed: id값을 이용해서 삭제된 원소임을 표시
    # removed[id] = True -> 삭제된 원소
    # removed[id] = False -> 삭제되지 않은 원소
    removed = [False]*1000001

    for __ in range(k):
        operation, num = input().split()
        num = int(num)

        if operation == 'I':
            heapq.heappush(min_heap, (num, id))
            # max_heap에 삽입할 때는 마이너스를 붙여서 삽입함에 유의!
            heapq.heappush(max_heap, (-num, id))
            # id값 + 1
            id += 1

        else:
            # 최대 제거
            if num == 1 and len(max_heap) > 0:
                while len(max_heap) > 0:
                    # 인덱스 0 원소의 id가 removed에 존재한다면 pop을 해버림 (삭제)
                    if removed[max_heap[0][1]]:
                        heapq.heappop(max_heap)
                        continue
                    # removed에 존재하지 않는다면
                    else:
                        # removed 배열에 기록한다
                        removed[max_heap[0][1]] = True
                        # pop을 해버림
                        heapq.heappop(max_heap)
                        # 반복 멈춤
                        break


            # 최소 제거
            elif num == -1 and len(min_heap) > 0:
                while len(min_heap) > 0:
                    # 인덱스 0 원소의 id가 removed에 존재한다면 pop을 해버림 (삭제)
                    if removed[min_heap[0][1]]:
                        heapq.heappop(min_heap)
                        continue
                    # removed에 존재하지 않는다면
                    else:
                        # removed 배열에 기록한다
                        removed[min_heap[0][1]] = True
                        # pop을 해버림
                        heapq.heappop(min_heap)
                        # 반복 멈춤
                        break

    # 출력
    # removed에 기록된 요소들을 전부 지우자
    # max_heap
    while len(max_heap) > 0:
        if removed[max_heap[0][1]]:
            heapq.heappop(max_heap)
        else:
            break
    # min_heap
    while len(min_heap) > 0:
        if removed[min_heap[0][1]]:
            heapq.heappop(min_heap)
        else:
            break

    # max_heap, min_heap 둘 중 하나라도 비어있으면 EMPTY
    if len(max_heap) == 0 or len(min_heap) == 0:
        print("EMPTY")
    else:
        print(-max_heap[0][0], end = " ")
        print(min_heap[0][0])

---

🧂아이디어

풀리지 않았던 풀이💦

🔽 재풀이 해서 풀렸던 풀이

• 엄청난 실패 끝에 풀렸던 풀이
• 실패 이유 1: 시간 복잡도가 높았던 풀이 방법
  (e.g., 잘못된 자료구조 사용, 리스트를 순회해서 어떤 값을 찾는 동작, ...)
• 실패 이유 2: 출력 시 오류 ("틀렸습니다")
  (e.g., 예를 들어, removed 상태가 True인 요소를 pop하지 않았다던가 하는 사소한 실수...)