[C/C++] 백준 11286: 절댓값 힙 (구조체와 연산자 오버로딩)

11286: 절댓값 힙 문제

https://www.acmicpc.net/problem/11286

11286번: 절댓값 힙

 

절댓값 힙 문제는 최소 힙 문제를 조금 변형시켜면 쉽게 풀 수 있다.

최소 힙 문제에서 priority_queue를 정의할 때 priority_queue<int,vector<int>,greater<int>> queue;를 사용해야 했다면

이 문제에서는 절댓값이 작은 순으로 heap을 정렬시켜야하므로 세번째 자리에 greater<int> 가 아닌  priority_queue<int,vector<int>,cmp> queue;와 같은 새로 정의한 구조체를 넣어줘야한다. 

 

참고로

priority_queue<int, vector<int>> q;에서 이 안에서 int는 큐에 들어갈 데이터의 타입을 말한다.

priority_queue<int, vector<int>> q;에서 vector<int>는 데이터들이 들어갈 컨테이너이다.

 

 

 

구조체와 연산자 오버로딩?

 

우리가 원하는대로 heap을 만들어주기 위해서 사용해야하는건 구조체와 연산자 오버로딩이다! 

struct는 내가 사용하고자하는 자료형을 임의로 정의하여 사용할 수 있는 "구조체"이며

bool operator<(const Data &b) const 이하 부분은 해당 구조체를 이용하여  sort를 할 때 무엇을 기준으로 할지 오버로딩해주는 부분이다. 여기서 오버로딩이란 내가 만든 사용자 정의 타입(sturct)에 관한 연산자를 정의하여 좀 더 편하게 사용할 수 있게 만드는 C++의 문법적 기능을 말한다. 

 

여기서 생각해야할 점은 priority_queue에서 각 원소들은 모두 구조체로 이루어져있다는 것이다. 즉

priority_queue <T,vector<T>,compare> pq에서 T는 구조체를 의미하는 것이다.

이때 compare은 우선 순위를 정의하는 구조체이기 때문에 구조체와 연산자 오버로딩을 이용하여 우선 순위를 정해줘야한다.

 

 또 compare 구조체에서 bool operator()을 재정의 했을 때 2번째 인자의 우선 순위가 높다면 true를 return하고 그렇지 않으면 false를 return 한다.

 

이와 관련된 내용은 아래의 블로그에 잘 정리되어 있어 공부하는데 큰 도움이 됐다!

https://codingdog.tistory.com/entry/c-priority-queue-%EC%98%88%EC%A0%9C-compare-%EA%B5%AC%EC%A1%B0%EC%B2%B4%EB%A7%8C-%EC%9E%98-%EC%A0%95%EC%9D%98%ED%95%A9%EC%8B%9C%EB%8B%A4

c++ priority queue 예제 : compare 구조체만 잘 정의합시다.

 

 

아래는 그 결과 이것들을 종합한 소스코드다!!

#include <iostream>
#include <iostream>
#include <algorithm>
#include<bits/stdc++.h>
#include<set>
#include <cmath>
#include<queue>

using namespace std; //모든 식별자가 고유하도록 보장하는 코드 영역

struct cmp{
  bool operator()(int a,int b)
 {      
    if(abs(a)==abs(b))
      return a>b;
    return abs(a)>abs(b);
  }
};


int main() {    
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  priority_queue<int,vector<int>,cmp> queue;
  int n;
  cin>>n;
  for(int i=0;i<n;i++)
    {
      int tmp;
      cin>>tmp;
      if(tmp)
        queue.push(tmp);
      else // 0일때
      {
        if(queue.empty())
          cout<<"0\n";
        else
        {
          cout<<queue.top()<<"\n";
          queue.pop();
        }
      }
    }
}