[백준] 7662번 이중 우선순위 큐
문제 링크
문제 설명
- I, N이 주어지면 N 삽입
- D, 1이 주어지면 최댓값 삭제
- D, -1이 주어지면 최솟값 삭제
- 연산 후 최댓값, 최솟값 출력
풀이
-
heapq로 최대힙, 최소힙을 만든다
-
I, N일 때
- 양쪽에 모두 삽입
- dict에 count += 1
-
D, 1일 때
- 최대 힙에서만 삭제
- dict에 count -= 1
-
D, -1일 때
- 최소 힙에서만 삭제
- dict에 count -= 1
삭제 구현 방법
- pop
- pop으로 나온 노드가 count > 0 일 경우 count -= 1 후 종료 (이미 삭제된 노드인지 판별)
- 아닐 경우 반복
- 만약 count == 0일 경우 dict에서 key를 제거 (이후 최대 최소를 탐색하지 않기 위해)
코드
import sys, heapq
ipt = sys.stdin.readline
opt = sys.stdout.write
t = int(ipt())
for _ in range(t):
k = int(ipt())
max_h, min_h = [], []
count_dict = dict()
for _ in range(k):
op, n = ipt().split()
n = int(n)
if op == 'I':
if n in count_dict:
count_dict[n] += 1
else:
count_dict[n] = 1
heapq.heappush(min_h, n)
heapq.heappush(max_h, -n)
elif op == 'D':
if n == 1:
while max_h:
c = -heapq.heappop(max_h)
if c in count_dict and count_dict[c] > 0:
count_dict[c] -= 1
if not count_dict[c]:
del count_dict[c]
break
else:
while min_h:
c = heapq.heappop(min_h)
if c in count_dict and count_dict[c] > 0:
count_dict[c] -= 1
if not count_dict[c]:
del count_dict[c]
break
if count_dict:
sorted_items = sorted(count_dict.items())
opt(f'{sorted_items[-1][0]} {sorted_items[0][0]}\n')
else:
opt('EMPTY\n')
Author And Source
이 문제에 관하여([백준] 7662번 이중 우선순위 큐), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@leehj8896/백준-7662번-이중-우선순위-큐
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
- I, N이 주어지면 N 삽입
- D, 1이 주어지면 최댓값 삭제
- D, -1이 주어지면 최솟값 삭제
- 연산 후 최댓값, 최솟값 출력
풀이
-
heapq로 최대힙, 최소힙을 만든다
-
I, N일 때
- 양쪽에 모두 삽입
- dict에 count += 1
-
D, 1일 때
- 최대 힙에서만 삭제
- dict에 count -= 1
-
D, -1일 때
- 최소 힙에서만 삭제
- dict에 count -= 1
삭제 구현 방법
- pop
- pop으로 나온 노드가 count > 0 일 경우 count -= 1 후 종료 (이미 삭제된 노드인지 판별)
- 아닐 경우 반복
- 만약 count == 0일 경우 dict에서 key를 제거 (이후 최대 최소를 탐색하지 않기 위해)
코드
import sys, heapq
ipt = sys.stdin.readline
opt = sys.stdout.write
t = int(ipt())
for _ in range(t):
k = int(ipt())
max_h, min_h = [], []
count_dict = dict()
for _ in range(k):
op, n = ipt().split()
n = int(n)
if op == 'I':
if n in count_dict:
count_dict[n] += 1
else:
count_dict[n] = 1
heapq.heappush(min_h, n)
heapq.heappush(max_h, -n)
elif op == 'D':
if n == 1:
while max_h:
c = -heapq.heappop(max_h)
if c in count_dict and count_dict[c] > 0:
count_dict[c] -= 1
if not count_dict[c]:
del count_dict[c]
break
else:
while min_h:
c = heapq.heappop(min_h)
if c in count_dict and count_dict[c] > 0:
count_dict[c] -= 1
if not count_dict[c]:
del count_dict[c]
break
if count_dict:
sorted_items = sorted(count_dict.items())
opt(f'{sorted_items[-1][0]} {sorted_items[0][0]}\n')
else:
opt('EMPTY\n')
Author And Source
이 문제에 관하여([백준] 7662번 이중 우선순위 큐), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@leehj8896/백준-7662번-이중-우선순위-큐
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
heapq로 최대힙, 최소힙을 만든다
I, N일 때
- 양쪽에 모두 삽입
- dict에 count += 1
D, 1일 때
- 최대 힙에서만 삭제
- dict에 count -= 1
D, -1일 때
- 최소 힙에서만 삭제
- dict에 count -= 1
- pop
- pop으로 나온 노드가 count > 0 일 경우 count -= 1 후 종료 (이미 삭제된 노드인지 판별)
- 아닐 경우 반복
- 만약 count == 0일 경우 dict에서 key를 제거 (이후 최대 최소를 탐색하지 않기 위해)
코드
import sys, heapq
ipt = sys.stdin.readline
opt = sys.stdout.write
t = int(ipt())
for _ in range(t):
k = int(ipt())
max_h, min_h = [], []
count_dict = dict()
for _ in range(k):
op, n = ipt().split()
n = int(n)
if op == 'I':
if n in count_dict:
count_dict[n] += 1
else:
count_dict[n] = 1
heapq.heappush(min_h, n)
heapq.heappush(max_h, -n)
elif op == 'D':
if n == 1:
while max_h:
c = -heapq.heappop(max_h)
if c in count_dict and count_dict[c] > 0:
count_dict[c] -= 1
if not count_dict[c]:
del count_dict[c]
break
else:
while min_h:
c = heapq.heappop(min_h)
if c in count_dict and count_dict[c] > 0:
count_dict[c] -= 1
if not count_dict[c]:
del count_dict[c]
break
if count_dict:
sorted_items = sorted(count_dict.items())
opt(f'{sorted_items[-1][0]} {sorted_items[0][0]}\n')
else:
opt('EMPTY\n')
Author And Source
이 문제에 관하여([백준] 7662번 이중 우선순위 큐), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@leehj8896/백준-7662번-이중-우선순위-큐
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
import sys, heapq
ipt = sys.stdin.readline
opt = sys.stdout.write
t = int(ipt())
for _ in range(t):
k = int(ipt())
max_h, min_h = [], []
count_dict = dict()
for _ in range(k):
op, n = ipt().split()
n = int(n)
if op == 'I':
if n in count_dict:
count_dict[n] += 1
else:
count_dict[n] = 1
heapq.heappush(min_h, n)
heapq.heappush(max_h, -n)
elif op == 'D':
if n == 1:
while max_h:
c = -heapq.heappop(max_h)
if c in count_dict and count_dict[c] > 0:
count_dict[c] -= 1
if not count_dict[c]:
del count_dict[c]
break
else:
while min_h:
c = heapq.heappop(min_h)
if c in count_dict and count_dict[c] > 0:
count_dict[c] -= 1
if not count_dict[c]:
del count_dict[c]
break
if count_dict:
sorted_items = sorted(count_dict.items())
opt(f'{sorted_items[-1][0]} {sorted_items[0][0]}\n')
else:
opt('EMPTY\n')
Author And Source
이 문제에 관하여([백준] 7662번 이중 우선순위 큐), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@leehj8896/백준-7662번-이중-우선순위-큐저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)