알고리즘/백준(BOJ) 문제풀이

[백준/BOJ] 11286번 : 절댓값 힙, 1655번 : 가운데를 말해요 (우선순위 큐)

restudy 2022. 3. 5. 23:57
반응형

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 11286번 : '절댓값 힙', 1655번 : '가운데를 말해요' 문제의 풀이 코드와 해설을 다루고 있습니다.

 

문제 난이도는 Solved.ac 기준 각각 Silver I, Gold II 티어에 해당하며, 문제를 풀이하기 위해 우선순위 큐에 대한 이해가 필요합니다.

 

 

11286번 : 절댓값 힙

 

입력된 N에 대해 N개의 입력값이 주어지고, 입력값 x가 0인 경우는 배열에서 절댓값이 가장 작은 값을 (절댓값이 작은 값이 여러 개인 경우 가장 작은 값을) 출력하고, 0이 아닌 경우는 그 값을 배열에 저장하는 쿼리를 수행하는 프로그램을 작성하는 문제입니다.

 

당연하겠지만 매번 정렬을 하고 원소를 탐색하면 시간 초과가 발생하도록 설계가 되어있으므로, 우선순위 큐를 활용하여 문제를 풀어주어야 합니다.

 

 

#include <bits/stdc++.h>
using namespace std;

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

    int N; cin >> N;

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pQueue;
    while(N--) {
        int x; cin >> x;
        if(x != 0) pQueue.push({abs(x), x});
        else {
            if(!pQueue.empty()) {
                cout << pQueue.top().second << "\n";
                pQueue.pop();
            }
            else cout << "0\n";
        }
    }
}

 

priority_queue의 선언 형식만 잘 알아두면 쉽게 해결이 가능합니다.

greater로 오름차순 정렬을 활용하여 문제를 풀이하기 위해서는, pair를 이용하여 먼저 절댓값으로 오름차순 정렬을 하고, 절댓값이 같은 원소들에 대해서는 second에 절댓값이 없는 원소를 넣어 크기 순으로 정렬되게 할 수 있습니다.

따라서 {abs(x), x}로 pair를 만들어 Priority Queue에 넣어서 하나씩 pop 해주면 됩니다.

 

 

 

 

1655번 : 가운데를 말해요

 

N개의 수가 입력되고 각 수가 입력될 때마다 지금까지 입력받은 수 중에서 중간값을 출력하는 문제입니다.

풀이 방법은 여러 가지가 있겠지만 탐색이 log N 시간에 가능한 힙을 두 개 이용해서 풀어주는 방법이 가장 깔끔합니다.

 

방법을 설명하자면, 원소를 입력받을 때 지금까지 입력받은 원소 중 절반은 최대 힙, 나머지 절반은 최소 힙에 저장합니다.

이 때 최대 힙의 모든 원소 < 최소 힙의 모든 원소가 성립하도록 저장해주면, 최대 힙의 top과 최소 힙의 top에는 항상 중간값이 저장됩니다.

개수를 맞추기 위해 원소 수가 홀수일 때는 최대 힙에 1개 더 많이 저장되도록 하고 최대 힙의 top 값을 가져오면 됩니다.

 

 

#include <bits/stdc++.h>
using namespace std;

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

    int N; cin >> N;

    priority_queue<int> maxHeap;
    priority_queue<int, vector<int>, greater<int>> minHeap;

    while(N--) {
        int x; cin >> x;

        if(maxHeap.size() == minHeap.size()) maxHeap.push(x);
        else minHeap.push(x);

        if(!maxHeap.empty() && !minHeap.empty() && maxHeap.top() > minHeap.top()) {
            int tempMax = maxHeap.top();
            int tempMin = minHeap.top();
            maxHeap.pop();
            minHeap.pop();
            maxHeap.push(tempMin);
            minHeap.push(tempMax);
        }

        cout << maxHeap.top() << "\n";
    }
}

 

 

풀이 아이디어를 코드로 구현하면 위처럼 됩니다.

원소를 하나 넣을 때마다 만약 최대 힙의 top 값이 최소 힙의 top 값보다 크다면 반으로 나누어 분리가 제대로 되지 않은 것이므로 최대 힙의 top 값이 최소 힙의 top 값보다 작거나 같을 때까지 각 Heap의 top 값을 계속 교환해주면 됩니다.

 

 

 

 

 

반응형