[백준/파이썬] 7662번

📍백준 7662 문제

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

코드

import heapq
import sys
input = sys.stdin.readline

testCase = int(input())

for _ in range(testCase):
    n = int(input())
    maxArr = []
    minArr = []
    visited = [1] * n
    for i in range(n):
        cmd, num = map(str, input().split())
        num = int(num)
        if cmd == 'I':
            heapq.heappush(minArr, (num, i))
            heapq.heappush(maxArr, (-num, i))
        else:
            if num == -1:
                if minArr:
                    visited[heapq.heappop(minArr)[1]] = 0
            elif num == 1:
                if maxArr:
                    visited[heapq.heappop(maxArr)[1]] = 0
        while minArr and visited[minArr[0][1]] == 0:
            heapq.heappop(minArr)
        while maxArr and visited[maxArr[0][1]] == 0:
            heapq.heappop(maxArr)
    if minArr == []:
        print("EMPTY")
    else:
        print(-maxArr[0][0], minArr[0][0])

풀이

• visited라는 배열을 만든다.
• minArr와 maxArr에 값을 저장할때, (num, i)형태로 값을 저장한다.
  (몇번째에 어떤 값이 추가되었는지 알기 위해!)
• 값을 지울 때, 몇번째에 들어온 값이 지워졌는지 알기 위해 visited[i] = 0으로 만들어준다.
• 만약 minArr 또는 maxArr에 visited[i]=0인 값이 존재한다면 값을 삭제한다.