[C++로 풀이] 최솟값 만들기⭐⭐

📌 최솟값 만들기

난이도 ⭐⭐

🚀 문제

최소값이 되려면 A에서의 최소값과 B에서의 최대값을 곱해야 최소값이 된다. 큰 것과 큰 것을 곱하면 값이 작아질리가 없기에 최대한 작은 것은 큰 것과 곱하도록 하는게 좋다. [1, 2, 3, 4, 5] 와 [10, 9, 8, 7, 6] 을 위 문제식으로 곱하고 누적합한 것의 최소값은 1 * 10 + 2 * 9 + 3 * 8 + 4 * 7 + 5 * 6 이 된다.

🚀 내 풀이

✈ 1차 풀이 (⏰시간초과)

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

int solution(vector<int> A, vector<int> B)
{
    int answer = 0;

    for (int i = 0; i < A.size(); i++)
    {
        vector<int>::iterator minOfA_iter = min_element(A.begin(), A.end());
        vector<int>::iterator maxOfB_iter = max_element(B.begin(), B.end());

        answer += *minOfA_iter * *maxOfB_iter;

        A.erase(minOfA_iter);
        B.erase(maxOfB_iter);
    }

    return answer;
}

매 반복마다 A의 최소값과 B의 최대값을 구하고 이 값들끼리 연산해준 후 A와 B에서 지우고.. 시간 초과가 나부렀다 ㅠㅠ 매 반복 안에서 최소값 최대값을 구해주고 erase도 해주므로 사실상 \(O(N^2)\) 나 마찬가지인 것이다.

✈ 2차 풀이 ⭕

#include <iostream>
#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 는 내림 차순 정렬해주면 각각 차례대로 앞부터 접근해오면 순차적으로 크기 순대로 접근할 수 있다. 딱 한번 이렇게 정렬해주면 일일이 매 반복마다 최소값 최대값을 구하고 erase 해줄 필요가 없는 것이다. 이 경우 O(N).

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

Programmers 카테고리 내 다른 글 보러가기