나는 최소힙이랑 최대힙 두 개를 만들어서 풀려했다.
처음에 내가 한 방법은
였는데 3번이 찝찝했었는데 역시 시간초과가 났다.
그래서 다른 사람들이 한 방법을 찾아보고 내 코드를 바꿔봤다.
i 번째에 insert('I')
된 노드의 delete('D')
여부(boolean)를 저장하는 리스트를 모두 False
로 초기화해놓고 나서
i
, 뒤에서는 idx
로 쓰인다)인지와 함께 튜플로 힙에 저장했다. for i in range(t):
op, opn = input().split()
opn = int(opn)
if op == 'I':
heapq.heappush(minH, (opn, i))
heapq.heappush(maxH, (-opn, i))
popped[idx]
가 True
인지) # 최댓값 삭제
if opn == 1:
# 이미 최소힙에서 pop된 애들일 경우 계속 삭제
while maxH and popped[maxH[0][1]]:
idx = heapq.heappop(maxH)[1]
if maxH: # 힙이 비어있지 않으면
idx = heapq.heappop(maxH)[1]
popped[idx] = True
이렇게 하면 'D' 연산을 할 때 한 쪽 힙에서만 지워도 제대로 결과를 낼 수 있다! 밑에 코드를 보자
import heapq
T = int(input())
result = []
for _ in range(T):
t = int(input())
minH = []
maxH = []
popped = [False for _ in range(t)]
for i in range(t):
op, opn = input().split()
opn = int(opn)
if op == 'I':
heapq.heappush(minH, (opn, i))
heapq.heappush(maxH, (-opn, i))
elif op == 'D':
if opn == 1:
while maxH and popped[maxH[0][1]]:
idx = heapq.heappop(maxH)[1]
if maxH:
idx = heapq.heappop(maxH)[1]
popped[idx] = True
else:
while minH and popped[minH[0][1]]:
idx = heapq.heappop(minH)[1]
if minH:
idx = heapq.heappop(minH)[1]
popped[idx] = True
while minH and popped[minH[0][1]]:
heapq.heappop(minH)
while maxH and popped[maxH[0][1]]:
heapq.heappop(maxH)
if not minH:
result.append('EMPTY')
else:
result.append(str(-heapq.heappop(maxH)[0])+' '+str(heapq.heappop(minH)[0]))
print('\n'.join(result))
주의해야 할 점은 연산을 모두 마치고 나서, 마지막 답으로 각 힙의 탑노드를 빼와야하기 때문에 마찬가지로 우선순위에 올라가있는 popped
가 True
인 노드들을 먼저 삭제해주어야 한다.
대신 그냥 맨 위의 애들만 체크 하면 되기 때문에 따로 idx
를 저장할 필요는 없고 삭제(heappop)만 해주면 된다.
하씨. 혹시나 해서 힙 한개만 써서 해봤는데 역시 시간초과다. 표준 입출력 써서 해두 시간초과다 파이썬 부들부들
# 시간초과
import heapq
import sys
input = sys.stdin.readline
print = sys.stdout.write
T = int(input())
result = []
for _ in range(T):
t = int(input())
h = []
for i in range(t):
op, opn = input().split()
opn = int(opn)
if op == 'I':
heapq.heappush(h, opn)
elif op == 'D':
if h:
if opn == 1:
h.pop()
else:
h.pop(0)
if not h:
result.append('EMPTY')
else:
maxSol = h.pop()
if h:
minSol = h.pop(0)
else:
minSol = maxSol
result.append(f'{maxSol} {minSol}')
print('\n'.join(result))
sys.stdout.flush()