글 읽기 - 우선순위 큐는 일반 벡터보다 처리속도가 느리나요?(c++)

ksoosung77 2년 전 0

우선순위 큐로 했는데 계속 시간초과나서 그냥 벡터로 하고 정리했더니 통과되네요

#include <iostream>
#include <queue>
#include <map>
#include <string>
#include <vector>
#include <deque>
#include <cmath>
#pragma warning(disable:4996)

using namespace std;

struct Node {
	int s = 0;
	int e = 0;
};
struct cmp {
	bool operator()(Node* A, Node* B) {
		if (A->s != B->s) {
			return A->s > B->s;
		}
		else return A->e > B->e;
	}
};
priority_queue < Node*, vector<Node*>, cmp>arr;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int t;
	int a, b;
	cin >> t;
	while (t--) {
		cin >> a >> b;
		Node* makeNode = new Node();
		makeNode->s = a;
		makeNode->e = b;
		arr.push(makeNode);
	}
	int s = arr.top()->s, e = arr.top()->e;
	int sum = 0;
	//cout << arr.top()->s << " " << arr.top()->e << "\n";
	arr.pop();
	while (arr.size()) {
		if (e < arr.top()->s) {
			sum += e - s;
			s = arr.top()->s;
			e = arr.top()->e;
		}
		else if (e < arr.top()->e) {
			e = arr.top()->e;
		}
		//cout << arr.top()->s << " " << arr.top()->e << "\n";
		arr.pop();
	}
	sum += e - s;
	cout << sum;
}

slah007 2년 전 1

size가 N인 pq의 push, pop은 O(log N)인 반면 vector의 push_back, pop_back은 amortized O(1)입니다. vector는 크기 관계를 생각하지 않고 자료를 넣거나 마지막 자료를 빼낼 수 있고 priority queue는 데이터를 넣고 여러 데이터 중 가장 큰 값을 찾거나 지우는 과정을 반복할 때 사용합니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

우선순위 큐는 일반 벡터보다 처리속도가 느리나요?(c++)

ksoosung77 2년 전 0

slah007 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말