백준 11286 절댓값 합 (C++)

안유태·2022년 12월 1일
0

알고리즘

목록 보기
85/239

11286번: 절댓값 합

우선순위 큐를 이용하는 문제이다. 우선순위 큐를 선언할 때 pair를 사용해 절댓값과 원본값을 저장해주었고 오름차순으로 정렬되도록 greater를 추가해주었다. 이렇게되면 top에 절댓값과 원본값이 가장 작은 값이 있게되고 이를 출력 후 pop해주었다.
우선순위 큐를 pair를 사용함과 동시에 greater를 사용한 것은 처음이라 찾아봤었다. 출력부분 \n이 아니라 endl로 해주니 시간초과가 났었다. 이부분을 조심하자.



#include <iostream>
#include <cmath>
#include <queue>

using namespace std;

int N, zero = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

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

    cin >> N;

    for (int i = 0; i < N; i++) {
        int a;
        cin >> a;
        if (a != 0) {
            pq.push({ abs(a), a });
        }
        else {
            if (pq.empty()) {
                cout << 0 << "\n";
            }
            else {
                cout << pq.top().second << "\n";
                pq.pop();
            }
        }
    }

    return 0;
}
profile
공부하는 개발자

0개의 댓글