최솟값 만들기

들어가는 말

길이가 같은 배열이 두 개 있으면 각 원소를 곱한 다음 더해서 최소값을 만드는 문제이다. 여기서 곱한 숫자는 지워진다. A배열의 최소와 B배열의 최대를 곱한 다음 더하면 최종적으로 최솟값이 나올 거라 생각했다. 때문에 algorithm에 있는 min_element와 max_element로 최소값과 최대값을 찾은 다음(min_element와 max_element는 위치를 반환하므로 포인터가 필요하다) 벡터이름.erase(min_element), 벡터이름.erase(max_element)로 사용한 최솟값과 최댓값을 지워주는 방식을 이용했다.
하지만, 정확성 테스트는 전부 통과했는데 효율성 테스트는 전부 실패하는 거 아닌가! 그래서 질문하기를 찾아보니 어떤 사람이 우선순위 큐로 풀었다는 답을 내놓았다. 그래서 나도 우선순위 큐로 풀었다.
큐는 후단에서 삽입하고 전단에서 삭제하는 자료구조이다. 여기서 우선순위를 붙인다면 조건에 우선적인 요소부터 먼저 삽입한다는 의미다. c++에서는 헤더파일 queue를 삽입하고 priority_queue 자료형을 이용해서 우선순위 큐를 만들면 된다. 우선순위 큐는 기본적으로 내림차순이나, priority_queue<int, vector int , greater int >를 사용한다면 오름차순으로도 만들 수 있다.

코드 설명

Apq는 오름차순의 우선순위 큐로 선언하고 Bpq는 내림차순의 우선순위 큐로 선언한다. 첫 번째 반복문으로 벡터의 사이즈만큼 돌면서 A의 요소와 B의 요소를 각 우선순위 큐의 기준에 맞게 삽입한다. 두 번째 반복문 또한 벡터의 사이즈만큼 돌면서 answer에 각 우선순위 큐의 첫 번째 요소를 곱한 다음에 더한다. 그리고 pop()을 이용해서 이용한 값을 우선순위 큐에서 지운다. 마지막으로 최종 결과값을 return하면 된다.

코드

#include <iostream>
#include<vector>
#include<queue>

using namespace std;
/*우선순위 큐*/
int solution(vector<int> A, vector<int> B)
{
    priority_queue<int, vector<int>, greater<int>> Apq;
    priority_queue<int> Bpq;
    int answer = 0;
    int size = A.size();
    
    for(int i=0; i<size; i++){
        Apq.push(A[i]);
        Bpq.push(B[i]);
    }
    
    for(int i=0; i<size; i++){
        answer = answer + (Apq.top() * Bpq.top());
        Apq.pop();
        Bpq.pop();
    }
    
    return answer;
}