Gidhub BE Developer

BOJ - 절대값 힙

2018-02-15
goodGid

Problem

Problem URL : 절대값 힙

Screenshots of Problem Explain

Answer Code (1) [18. 02. 15]


#include<iostream>
#include<algorithm>
#include<queue>
#include<functional>
#define ll long long
using namespace std;

// Root is Max Value
//priority_queue<int> pq;
//priority_queue<int,vector<int>,less<int> > pq;

// Root is Min Value
priority_queue<int,vector<int>,greater<int> > _pq;
priority_queue<int,vector<int>,greater<int> > pq;

void print(int i){
    if( i == 1){
        printf("%d\n",pq.top());
        pq.pop();
    }
    else{
        printf("-%d\n",_pq.top());
        _pq.pop();
    }
}

int main(void) {
    int tc;
    cin >> tc;
    
    while (tc--) {
        int a;
        scanf("%d",&a);
        
        if( a==0 ){
            if( pq.empty() && _pq.empty())
                printf("0\n");
            
            else {
                if( pq.empty())
                    print(0);
                else if( _pq.empty())
                    print(1);
                else{
                    if( pq.top() < _pq.top() )
                        print(1);
                    else
                        print(0);
                }
            }
        }
        else{
            if( a < 0 )
                _pq.push( a * -1);
            else
                pq.push(a);
        }
    }
    
    return 0;
}



Answer Code (2) [18. 02. 15]


#include <cstdio>
#include <cmath>
#include <queue>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;
typedef pair <int, int> p;

priority_queue <p, vector<p>, greater<p>> pq;

int main() {
    int n; scanf("%d", &n);
    while (n--) {
        int x; scanf("%d", &x);
        if (x) pq.push(p{ abs(x), x });
        else {
            if (pq.empty()) printf("0\n");
            else {
                printf("%d\n", pq.top().second);
                pq.pop();
            }
        }
    }
    return 0;
}


Code Review

Answer Code (1) [18. 02. 15]

  • if로 해결한 문제 …

  • 문제 의도를 잘 파악 못하겠다. 정말 if분기를 하여서 풀라는것인가 ? 흠 …


Answer Code (2) [18. 02. 15]

  • Code Review하면서 찾은 (내 생각) 좋은 Code.

  • pair인 경우 greater<> 비교를 어떻게하는지 생각해 볼 수 있는 Code이다.


Comments

Content