우선순위 큐 연습문제 풀기

기본적으로 PQ를 선언하면 최대 힙으로 설정된다. 최소 힙으로 바꾸려면 priority_queue의 세 번째 인자로 greater<> 을 달아주면 된다.

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

1927번: 최소 힙

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

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    priority_queue<int, vector<int>, greater<>> PQ;
    int n; cin>>n;
    while(n--){
        int x; cin>>x;
        if(x) PQ.push(x);
        else{
            if(PQ.empty()) cout<<"0\n";
            else{
                cout<<PQ.top()<<'\n';
                PQ.pop();
            }
        }
    }
    return 0;
}

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

11279번: 최대 힙

#include <bits/stdc++.h>
using namespace std;
int ans;
int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    priority_queue<int,vector<int>> PQ;
    int n; cin>>n;
    while(n--){
        int x; cin>>x;
        if(x==0){
            if(PQ.empty()) cout<<"0\n";
            else{
                cout<<PQ.top()<<'\n';
                PQ.pop();
            }
        }
        else PQ.push(x);
    }
    return 0;
}

---

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

11286번: 절댓값 힙

최소 힙과 비슷한 문제인데 음수가 들어오기에 비교를 해줄 cmp를 따로 구현해주어야 한다. 

a를 앞에, b를 뒤에 놓을 경우 true를 반환하게, 

b를 앞에, a를 뒤에 놓을 경우 false를 반환하게 구현한다.

해당 코드는 내림차순으로 구현해야 하므로 abs(a)>abs(b)로 했다.

절대값 부호를 씌운 두 수가 같을 경우에는 a가 양수일 경우 a가 앞에 와야 하므로 이런 식으로 구현했다.처음에는 많이 햇갈렸는데 많이 보니까 적응된다.

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

class cmp{
public:
    bool operator() (int a, int b){ //앞에 놓고 싶은 것, 뒤에 놓고 싶은 것 -> true
        if(abs(a)!=abs(b)) return abs(a)>abs(b);
        return a>0 && b<0;
    }
};

priority_queue<int,vector<int>,cmp> PQ;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n; cin>>n;
    while(n--){
        int x; cin>>x;
        if(x!=0) PQ.push(x);
        else{
            if(PQ.empty()) cout<<0<<'\n';
            else{
                cout<<PQ.top()<<'\n';
                PQ.pop();
            }
        }
    }
    return 0;
}

 

---

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

2075번: N번째 큰 수

메모리 제한이 작기 때문에 필요한 만큼만 데이터를 저장하는 테크닉이 필요

#include <bits/stdc++.h>
using namespace std;
int ans;
int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    priority_queue<int,vector<int>,greater<>> PQ;
    int n; cin>>n;
    for(int i=0;i<n*n;i++){
        int x; cin>>x; PQ.push(x);
        if(PQ.size()>n) PQ.pop();
    }
    cout<<PQ.top();
    return 0;
}

//작은게 front에 몰릴 것임
//pop을 한다는 말은 가장 작은 값을 뽑아낸다는 의미
//우선순위 큐에 담긴 값의 수가 n개를 넘기면 가장 작은 값을 뽑아내서 크기를 유지함
//모든 과정이 끝나고 우선순위 큐의 top <- 제일 끝
//을 출력하면 5번째로 큰 값이 출력됨

---

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

1715번: 카드 정렬하기

그리디는 최흉최악의 알고리즘...

항상 이 그리디 알고리즘이 올바르다고 생각하면 아니고, 아니라고 생각하면 맞는 그런 문제들이다...

그래도 이 카드 정렬하기는 간단한 문제였다.

가장 작은 수 두 개를 더한 값을 ans에 더하고, 그 두 수를 지우고 그 두 수를 더한 값을 큐에 집어넣는다.

#include <bits/stdc++.h>
using namespace std;
int ans;
int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    priority_queue<int, vector<int>, greater<>> PQ;
    int n; cin>>n;
    while(n--){
        int x; cin>>x;
        PQ.push(x);
    }
    while(PQ.size()>1){
        int a=PQ.top(); PQ.pop();
        int b=PQ.top(); PQ.pop();
        PQ.push(a+b); ans+=(a+b);
    }
    cout<<ans;
    return 0;
}

---

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

13975번: 파일 합치기 3

카드 정렬하기와 다를 것이 없는 문제이다.

이 알고리즘을 허프만 부호화라고 한다고 한다.

https://ko.wikipedia.org/wiki/%ED%97%88%ED%94%84%EB%A8%BC_%EB%B6%80%ED%98%B8%ED%99%94

허프먼 부호화 - 위키백과, 우리 모두의 백과사전

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    int t; cin>>t;
    while(t--){
        ll ans=0;
        priority_queue<ll, vector<ll>, greater<ll>> pq;
        int n; cin>>n;
        while(n--){
            int x; cin>>x;
            pq.push(x);
        }
        while(pq.size()>1){
            ll a=pq.top(); pq.pop();
            ll b=pq.top(); pq.pop();
            ans+=(a+b);
            pq.push(a+b);
        }
        cout<<ans<<'\n';
    }
    return 0;
}

---