Do it! 알고리즘 코딩테스트 | 1. 자료구조 - 스택과 큐 | 014 절댓값 힙 구현하기

문제 정보 백준 11286번 절댓값 힙 https://www.acmicpc.net/problem/11286

 

문제

절댓값 힙은 다음과 같은 연산을 지원하는 자료구조이다.

1. 배열에 정수 x (x ≠ 0)를 넣는다.
2. 배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다.

프로그램은 처음에 비어있는 배열에서 시작하게 된다.

입력

첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 절댓값이 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 정수는 -231보다 크고, 231보다 작다.

출력

입력에서 0이 주어진 회수만큼 답을 출력한다. 만약 배열이 비어 있는 경우인데 절댓값이 가장 작은 값을 출력하라고 한 경우에는 0을 출력하면 된다.

예제 입력 1 

18
1
-1
0
0
0
1
1
-1
-1
2
-2
0
0
0
0
0
0
0

예제 출력 1 

-1
1
0
-1
-1
1
1
-2
2
0

 

//내 코드
#include<iostream>
#include<algorithm>
using namespace std;
int queue[100000], front = -1, rear = -1;
void push(int v){
    queue[++rear] = v;
}
void pop(){
    cout << queue[++front] << endl;
}
int main(){
    int n, a[100000];
    cin >> n;
    for(int i=0; i<n; i++){
        cin >> a[i];
        if(a[i] != 0){
            push(a[i]);
            sort(queue, queue+rear+1);
        }
        else{
            if(front == rear)
                cout << "0" << endl;
            else
                pop();
        }
    }
}

 

//정답 코드
#include <iostream>
#include <queue>
using namespace std;

struct compare {
    bool operator()(int o1, int o2) {
        int first_abs = abs(o1);
        int second_abs = abs(o2);
        if (first_abs == second_abs)
            return o1 > o2;// 절대값이 같은 경우 음수 우선 정렬
        else
            return first_abs > second_abs;// 절대값을 기준으로 정렬
    }
};

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    // 우선순위 큐 선언방식: <자료형, 구현체, 비교함수명>
    priority_queue<int, vector<int>, compare> MyQueue;

    int N;
    cin >> N;
    for (int i = 0; i < N; i++) {
        int request;
        cin >> request;
        if (request == 0) {
            if (MyQueue.empty()) {
                cout << "0\n";
            }
            else {
                cout << MyQueue.top() << '\n';
                MyQueue.pop();
            }
        }
        else {
            MyQueue.push(request);
        }
    }
}

 

문제 자체는 쉬운데 절댓값 조건대로 큐를 정렬하는 것이 많이 어렵다..

 

struct compare {
    bool operator()(int o1, int o2) {
        int first_abs = abs(o1);
        int second_abs = abs(o2);
        if (first_abs == second_abs)
            return o1 > o2;// 절대값이 같은 경우 음수 우선 정렬
        else
            return first_abs > second_abs;// 절대값을 기준으로 정렬
    }
};

 

// 우선순위 큐 선언방식: <자료형, 구현체, 비교함수명>
priority_queue<int, vector<int>, compare> MyQueue;

 

이렇게 compare 구조체를 정의해 주어 절댓값 기준에 맞게 정렬을 해주면 되는데 이런 방법을 생각도 못해봤고 딱히 다시 쓸 것 같진 않다