[Programmers, C++]#Level2_최솟값 만들기, 우선순위 큐, 최소 힙, 최대 힙, 완전 이진 트리

#1. 문제

프로그래머스

 

---

 

#2. 풀이

 

1. 우선순위 큐

[자료구조]#7_우선순위 큐

우선순위 큐는 각 항목에 우선순위를 부여하고, 우선순위가 가장 높은 항목이 먼저 제거되는 자료구조입니다. 일반적으로, 최소/최대 힙으로 구현 가능하며 완전 이진트리의 한 종류입니다. 우선순위 큐는 우선순위가 가장 높은 항목만 접근 가능하며, 삽입/삭제 작업 시 내부적으로 반 정렬된 상태를 유지하여 O(log n)의 시간 복잡도를 갖습니다.

 

1. 최소 힙 우선순위 큐 + 최대 힙 우선순위 큐

1. 누적합이 최소가 되려면 A 배열의 현재 뽑을 수 있는 최대 값과 B 배열의 현재 뽑을 수 있는 최소 값을 곱하여 누적합에 더해주어야 합니다.
2. 두 개의 우선순위 큐를 활용하여, 각각 최소 힙 우선순위 큐, 최대 힙 우선순위 큐로 선언하고, A 배열과 B배열의 원소들을 삽입해줍니다.
3. 그리고, 두 우선순위 큐가 빌 때까지, 최소 힙의 top과 최대 힙의 top을 곱해 누적합에 더해주면 됩니다.

 

---

 

#3. 코드

/*
    @링크: https://school.programmers.co.kr/learn/courses/30/lessons/12941
    @문제: 최솟값 만들기
    @설명
        1. 우선순위 큐
        2. 최소 힙과 최대 힙
*/
#include <iostream>
#include<vector>
#include <queue>
using namespace std;
int solution(vector<int> A, vector<int> B)
{
    int answer = 0;
    //@최대 힙
    priority_queue<int, vector<int>> pq1;
    //@최소 힙
    priority_queue<int, vector<int>, greater<int>> pq2;
    for(int i=0; i<(int)A.size(); ++i)
    {
        pq1.push(A[i]);
        pq2.push(B[i]);
    }
    while(!pq1.empty() && !pq2.empty())
    {
        int Acur = pq1.top();
        int Bcur = pq2.top();
        pq1.pop();
        pq2.pop();
        answer += Acur * Bcur;
    }
    return answer;
}

 

---