11286_절댓값 힙

Concept & Idea

우선순위큐를 너무 오랜만에 사용하다 보니.. 솔직히 말하면 다익스트라 문제 풀때나 조금 사용해봐서 낯설다 ㅎ
직접 Comp 함수 구현해서 Sort 하도록 한게 너무 오랜만이라 가져와 본 문제이다. 

문제는 위 사진을 읽기만 해도 무슨 문제인지 알 것 이다.

priority_queue를 pair<int, int> 형으로 제작했다.  {절댓값, 원값} 의 형태로!
comp 함수를 정의해서 내가 Sort하는 순서를 정할 수 있는데, 
절댓값이 같을 땐 원값이 작은 순으로, 그 외에는 절댓값 순으로 소팅되는 형태이다. 

comp 함수 작성하는 데에 생각보다 시간이 오래걸린 거 같다. :( 아쉬운 마음 그득,,  

Code

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
struct comp{
    bool operator()(pair<int, int> a, pair<int, int> b) {
        if (a.first == b.first) {
            return a.second > b.second;
        }
        return a.first > b.first;
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin>>n;
    priority_queue<pair<int, int>, vector<pair<int, int>>, comp> pq; //{절대값, 원값}
    for(int i=0; i<n; i++) {
        int num;
        cin>>num;
        if(num==0) {
            if(pq.empty())
                cout<<0<<"\n";
            else {
                cout<<pq.top().second<<"\n";
                pq.pop();
            }
        } else {
            int absolute_num = num>0 ? num : -num;
            pq.push({absolute_num, num});
        }
        
    }
    
}

 

Fealing

C++이 다시 손에 익기 시작했다. 
알고리즘 문제 해결 전략이라는 책을 읽으려 예전부터 계획했었는데, 이번 기회에 기본적인 개념을 좀 잡아야 할 것 같다.

아자자자자자자자!