cejung   6달 전

시간 초과 질문드립니다.

priority queue를 사용할 때, pair와 struct가 어떤 시간 차이가 있는지 궁금합니다.


pair<int, pair<int, int>>를 사용하고 cmp 대신 아래 코드 처럼 priority queue를 작성하는 경우 시간초과가 발생하지 않습니다.

priority_queue<pair<int,pair<int,int>>, vector<pair<int,pair<int,int>>>, greater<pair<int,pair<int,int>>>> pq


반면, 아래 코드 처럼 struct Node를 사용하고 cmp 구조체를 사용하면 시간초과가 발생합니다.

struct Node{
    int w, r, c;
};

struct cmp{
    bool operator()(Node a, Node b){
        if(a.r == b.r && a.c == b.c){
            if(a.w > b.w) return true;
        }
    }
};

priority_queue<Node, vector<Node>, cmp> pq;

어떤 차이가 있는 것인지 궁금합니다.

소스 코드는 시간 초과가 난 소스 입니다.

yuris   6달 전

cmp 구조체 에서 r과 c가 같지 않으면 아무런 반환을 하지 않습니다.

cejung   6달 전

@yuris

답변감사드립니다.

해당 코드에서 첫번째 if 문 지워도 시간초과는 똑같이 나네요 ㅠㅠ

struct cmp{
bool operator()(Node a, Node b){
if(a.r == b.r && a.c == b.c){
if(a.w > b.w) return true;
}
}
};

yuris   6달 전

if문을 지워도 (a.w > b.w)조건이 맞지 않으면 값을 반환하지 않습니다. 조건에 맞지 않는 경우에 false값을 반환해줘야 제대로 된 비교 함수로 사용될 수 있습니다.

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