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

최솟값 만들기

문제 링크

최솟값 만들기

분석

A, B 배열의 길이는 같고, 자연수로 이루어져 있습니다.

해당 배열에서 각각 숫자를 한개씩 선택하고, 두 수를 곱하는 과정을 배열의 길이만큼 반복합니다.
이 과정에서 곱한 값을 누적해야합니다.
이러한 과정으로 계산했을 때 최소가 되는 값을 찾아 반환해야합니다.

즉, 배열의 모든 수를 서로 곱해 결과 값을 누적해야합니다.

곱셈으로 한번 사용한 값은 다시 사용하지 않습니다.

문제의 설명과 입출력 예를 보면 다음과 같습니다.

A = [1, 4, 2], B = [5, 4, 4] 일때,

A에서 첫 번째 숫자 1, B에서 첫 번째 숫자 5를 곱해 누적,
A에서 두 번째 숫자 4, B에서 세 번째 숫자 4를 곱해 누적,
A에서 세 번째 숫자 2, B에서 두 번째 숫자 4를 곱해 누적

A = [1, 2], B = [3, 4] 일때,

A에서 첫 번째 숫자 1, B에서 두 번째 숫자 4를 곱해 누적,
A에서 두 번째 숫자 2, B에서 첫 번째 숫자 3을 곱해 누적

이 예시를 볼 경우 A에서는 가장 값이 작은 자연수를 우선적으로 선택하고, B에서는 가장 값이 큰 자연수를 우선적으로 선택하는 것을 알 수 있었습니다.

이를 통해 저는 A와 B배열을 각각 오름차순, 내림차순 정렬해주고 각 자연수를 순서대로 곱해 최소값을 구해주었습니다.
이렇게 하면 A에서 작은 수는 B에서 큰 수와 곱해주게 되고, A에서 큰 수는 B에서 작은 수와 곱하게 됩니다.

풀이

#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<int> A, vector<int> B)
{
    int answer = 0;
    
    // A 배열 오름차순
    sort(A.begin(), A.end(), less<int>());

    // B 배열 내림차순
    sort(B.begin(), B.end(), greater<int>());
    
    // A배열을 기준으로 순회
    for (int i = 0; i < A.size(); ++i)
    {
        answer += A[i] * B[i];
    }

    return answer;
}

성능 요약

시간 복잡도는 $O(n log n)$입니다.

• 배열 정렬 $O(n log n)$
• 배열을 순회하는 반복문 $O(n)$
• $O(n log n) + O(n)$

공간 복잡도는 $O(log n)$입니다.

• 배열 정렬 중 재귀 호출 스택에 의해 $O(log n)$

테스트 성능

정확성 테스트

테스트 1 〉 통과 (0.01ms, 4.28MB)
테스트 2 〉 통과 (0.02ms, 4.14MB)
테스트 3 〉 통과 (0.01ms, 4.22MB)
테스트 4 〉 통과 (0.01ms, 4.2MB)
테스트 5 〉 통과 (0.01ms, 4.13MB)
테스트 6 〉 통과 (0.01ms, 4.12MB)
테스트 7 〉 통과 (0.01ms, 4.21MB)
테스트 8 〉 통과 (0.01ms, 4.21MB)
테스트 9 〉 통과 (0.01ms, 4.21MB)
테스트 10 〉 통과 (0.01ms, 3.63MB)
테스트 11 〉 통과 (0.01ms, 4.21MB)
테스트 12 〉 통과 (0.01ms, 3.68MB)
테스트 13 〉 통과 (0.01ms, 3.69MB)
테스트 14 〉 통과 (0.01ms, 4.21MB)
테스트 15 〉 통과 (0.01ms, 4.44MB)
테스트 16 〉 통과 (0.01ms, 4.2MB)

효율성 테스트

테스트 1 〉 통과 (0.09ms, 3.81MB)
테스트 2 〉 통과 (0.08ms, 3.8MB)
테스트 3 〉 통과 (0.08ms, 3.85MB)
테스트 4 〉 통과 (0.08ms, 3.81MB)