문제 링크
https://www.acmicpc.net/problem/7662
7662번: 이중 우선순위 큐
입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적
www.acmicpc.net
풀이
- heapq을 사용해서 풀었는데 시간초과가 발생하였다.
- 파이썬 힙의 경우 popleft()은 실행이 불가능하고 최소힙만 지원하기 때문에
I 명령일 경우 최소힙에 숫자를 삽입하였다.
D -1 일 경우, 최소힙에서 Pop 명령어를 통해 최솟값을 제거하였다.
D 1 일경우, 최소힙에서 heapq.nlargest(1, heap) 명령어를 통해 가장 큰 값 1개를 불러오고 이 후 remove 명령어를 통해 힙에서 제거해줬다.
+ heapq.nlargest(n, heap) : heap에서 가장 큰 값 n개를 담고 있는 리스트 반환
import heapq
import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
n = int(input())
heap = []
for i in range(n):
s = input().split()
if s[0] == 'I':
heapq.heappush(heap,int(s[1]))
if s[0] == 'D':
if heap :
# 최솟값 삭제
if s[1] == '-1':
heapq.heappop(heap)
else :
# 최댓값 반환 후 삭제
num = heapq.nlargest(1, heap)[0]
heap.remove(num)
if heap:
print(max(heap), min(heap))
else:
print('EMPTY')
- 최소힙, 최대힙 두개의 큐로 구현해보았다. 두 개의 힙을 동기화 하는 부분은 다른 블로그를 참고 했다 ㅠㅠ
파이썬에서 최대힙은 부호를 변경하여 대입해주면 된다.
exist[id] : 인덱스는 입력된 숫자의 고유 번호이다.
- 숫자를 삽입할 땐 exist[id]를 True로 변경한다.
- 숫자를 삭제할 땐
최소힙과 최대힙의 숫자들을 동기화 시켜줘야 하기 때문에 exist[id]가 False인데 큐에 존재한다면 pop()을 통해 제거해준다.
D -1 일 경우 최소힙이 비어있지 않으면 최솟값을 제거한다.
D 1 일 경우 최대힙이 비어있지 않으면 최댓값을 제거한다.
- 마지막 출력 전에도 동기화를 시켜주고 힙에 숫자가 남아있다면 최댓값과 최솟값을 출력한다.
최댓값의 경우 max_heap에 마이너스 부호를 붙여주고 삽입했기 때문에 마이너스 부호를 붙여 출력한다.
- 어렵다 ..
import heapq
import sys
input = sys.stdin.readline
# 동기화
def sync(h):
while h and not exist[h[0][1]]:
heapq.heappop(h)
t = int(input())
for _ in range(t):
n = int(input())
max_heap = []
min_heap = []
# 인덱스는 입력된 숫자의 고유 번호
exist = [False] * 1000001
for i in range(n):
s, num = input().split()
num = int(num)
if s== 'I':
heapq.heappush(max_heap, (-int(num), i))
heapq.heappush(min_heap, (int(num), i))
# 존재함을 표시
exist[i] = True
if s == 'D':
if num == -1 :
sync(min_heap)
if min_heap:
exist[min_heap[0][1]] = False
heapq.heappop(min_heap)
else :
sync(max_heap)
if max_heap :
exist[max_heap[0][1]] = False
heapq.heappop(max_heap)
sync(max_heap)
sync(min_heap)
if max_heap and min_heap:
print(-max_heap[0][0], min_heap[0][0])
else:
print('EMPTY')
'개발 > algorithm' 카테고리의 다른 글
[백준 9019번] DLSR - python (0) | 2022.02.18 |
---|---|
[백준 10026번] 적록색약 - python (0) | 2022.02.17 |
[백준 7569번] 토마토 - python (0) | 2022.02.17 |
[백준 7576번] 토마토 -python (0) | 2022.02.17 |
[백준 5430번] AC - python (0) | 2022.02.17 |