목록priority queue (1)

Doby's Lab

[자료구조] 백준 7662번: 이중 우선순위 큐 (C++), 두 큐를 하나처럼, 싱크의 핵심

입력값을 넣을 때마다 즉각적으로 정렬을 시키면 되는 문제가 아닐까를 생각했지만 정렬의 시간 복잡도 O(NlogN), 연산의 최대 개수가 1,000,000이므로 이는 시간 초과를 발생시킨다. 즉, 이번 문제에서는 우선순위 큐(priority queue)의 사용을 유도한다. 큐의 특성상 pop(D)를 할 때는 앞에서 밖에 할 수 없기 때문에 두 개의 우선순위 큐를 선언해주었다. 오름차순과 내림차순. 두 개의 큐를 선언하여 풀었던 코드는 다음과 같다. #include #include #include #include #define ll long long using namespace std; int main() { int T; cin >> T; for (int i = 0; i < T; i++) { int n; c..
PS/BOJ 2021. 10. 21. 12:21
이전 Prev 1 Next 다음