내용으로 건너뛰기
테페리넷
사용자 도구
등록
로그인
사이트 도구
검색
도구
문서 보기
Fold/unfold all
역링크
미디어 관리자
사이트맵
등록
로그인
>
미디어 관리자
사이트맵
현재 위치:
테페리넷
»
Problem Solving
»
문제
»
백준 온라인 저지 (BOJ)
»
이중 우선순위 큐
ps:problems:boj:7662
이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.
====== 이중 우선순위 큐 ====== ===== 풀이 ===== * [[ps:우선순위큐#Double-ended priority queue]] 를 만드는 문제. * 링크에서 설명했듯이 다양한 방법이 있지만, 여기에서는 가장 심플한 방법인 min heap과 max heap을 UpdatableHeap로 만들어서 사용했다. * n번의 삽입 삭제가 일어날때, 각각은 O(logn)에 처리되니 총 시간 복잡도는 O(nlogn). * 그러나 실제 제출된 코드들을 보면, 그냥 deque를 정렬된 상태로 유지해서, 삽입을 O(n)으로 처리하는 코드가 시간복잡도는 느리지만 더 빠르게 동작했다.; ===== 코드 ===== <dkpr py> """Solution code for "BOJ 7662. 이중 우선순위 큐". - Problem link: https://www.acmicpc.net/problem/7662 - Solution link: http://www.teferi.net/ps/problems/boj/7662 """ import sys from teflib import priorityqueue def main(): T = int(sys.stdin.readline()) for _ in range(T): max_heap = priorityqueue.UpdatableHeap() min_heap = priorityqueue.UpdatableHeap() k = int(sys.stdin.readline()) for _ in range(k): op, n = sys.stdin.readline().split() if op == 'I': num = int(n) max_heap.push(-num) min_heap.push(num) elif max_heap: if n == '1': num = -max_heap.pop() min_heap.delete(num) elif n == '-1': num = min_heap.pop() max_heap.delete(-num) if max_heap: print(-max_heap.top(), min_heap.top()) else: print('EMPTY') if __name__ == '__main__': main() </dkpr> * Dependency: [[:ps:teflib:priorityqueue#UpdatableHeap|teflib.priorityqueue.UpdatableHeap]] {{tag>BOJ ps:problems:boj:골드_5}}
ps/problems/boj/7662.txt
· 마지막으로 수정됨: 2022/06/29 02:34 저자
teferi
문서 도구
문서 보기
역링크
Fold/unfold all
맨 위로