[프로그래머스] 최솟값 만들기 with C++

문제 설명

---

제한 사항 및 입출력 예제

---

개념

　두 수열 A와 B의 각 원소를 한 번씩 곱한 값을 더했을 때, 그 합이 최소가 되도록 만드는 문제다. 즉, 한 수열에서 최솟값을 다른 수열에서의 최댓값과 곱하는 과정을 반복하여 합을 최소화하는 것이 목표다. 이를 구현하는 방법은 여러 가지가 있다. 

---

풀이 (1) multiset 활용

#include <vector>
#include <set>
using namespace std;

int solution(vector<int> A, vector<int> B)
{
    int answer = 0;
    multiset<int> ms1(A.begin(), A.end()), ms2(B.begin(), B.end());

    while (!ms1.empty())
    {
        answer += (*ms1.begin() * *ms2.rbegin());
        ms1.erase(ms1.begin());
        ms2.erase(prev(ms2.end()));
    }

    return answer;
}

　multiset은 최댓값과 최솟값에 바로 접근할 수 있는 자료구조다. 따라서 answer에 배열 A의 시작 지점(최솟값)과 배열 B의 끝 지점(최댓값)에 접근하여 값을 곱한 후, answer에 누적해서 더해주면 된다. 

---

풀이 (2) sort 활용

#include <vector>
#include <algorithm>
using namespace std;

int solution(vector<int> A, vector<int> B)
{
    int answer = 0;
    sort(A.begin(), A.end());
    sort(B.begin(), B.end(), greater<int>());

    for (int i = 0; i < A.size(); ++i)
        answer += (A[i] * B[i]);

    return answer;
}

　배열 A와 B를 각각 오름차순, 내림차순으로 정렬한 후에, 같은 위치에 있는 원소들을 곱하여 그 합을 계산한다.