📜 접근 방법
I n : n 삽입
D -1 : 최소값 삭제
D 1 : 최댓값 삭제
최댓값과 최솟값을 넣는 배열을 만들고 삽입 시 두 배열에 넣어주는데 인덱스와 함께 넣어준다.
또한 check_num으로 숫자를 삭제했는지 확인하는 배열로 삽입시에는 True로 변경하고 삭제시엔 False로 변경한다.
-> 이렇게 하는 이유는 최솟값과 최댓값을 삭제할 시에 어떤 값을 삭제했는지 서로 모르기 때문이다.
❌ 실패 코드
삭제시에 양쪽 우선순위 큐에서 동시에 같은 값을 삭제를 하려고 해서 풀지 못했다.
✅ 정답 코드
import sys
import heapq
t = int(sys.stdin.readline())
for i in range(t):
max_heap = []
min_heap = []
n = int(sys.stdin.readline())
check_num = [False] * n
for num_index in range(n):
w, num = sys.stdin.readline().split()
num = int(num)
if w == "I":
# 값 삽입
heapq.heappush(min_heap, (num, num_index))
heapq.heappush(max_heap, (-num, num_index))
check_num[num_index] = True
elif w == "D":
if num == 1:
# 최대값 삭제
while max_heap:
output, index = heapq.heappop(max_heap)
if check_num[index] == True:
check_num[index] = False
break
elif num == -1:
# 최소값 삭제
while min_heap:
output, index = heapq.heappop(min_heap)
if check_num[index] == True:
check_num[index] = False
break
while min_heap and check_num[min_heap[0][1]] == False:
heapq.heappop(min_heap)
while max_heap and check_num[max_heap[0][1]] == False:
heapq.heappop(max_heap)
if min_heap and max_heap:
print(-max_heap[0][0], min_heap[0][0])
else:
print("EMPTY")
💡알게 된점
2개의 우선순위 큐를 사용하는 것은 알았는데 삭제시에 양쪽 우선순위 큐에서 동시에 같은 값을 삭제를 해줘야하는데 그부분을 어떻게 짜야할지 어려웠다.
'코딩테스트 > Python' 카테고리의 다른 글
[python 백준 2109] 순회강연 (0) | 2023.04.09 |
---|---|
[python 백준 2696] 중앙값 구하기 (0) | 2023.04.09 |
[python] 혼자서 하는 틱택토 (0) | 2023.04.07 |
[python 백준 1374] 강의실 (0) | 2023.04.07 |
[python] pccp 모의고사 2 실습용 로봇 (0) | 2023.03.22 |