프로그래머스 최솟값 만들기 JAVA 풀이 (그리디, 정렬)

🔗 문제 링크

프로그래머스

---

📌 문제 개요

길이가 같은 두 배열 A, B가 주어진다.

각 배열에서 숫자를 하나씩 선택하여 곱한 뒤 누적 합을 구한다.

 

모든 원소를 한 번씩만 사용해야 하며, 최종 누적 합이 최소가 되도록 만들어야 한다.

---

📌 접근 방법

처음에는 같은 인덱스의 값끼리 곱하면 된다고 생각할 수 있다.

하지만 이렇게 하면 최솟값이 보장되지 않는다.

 

예를 들어, 같은 인덱스끼리 곱하면

A = [1, 2]
B = [3, 4]
1 * 3 + 2 * 4 = 11

 

반면 아래와 같이 작업시 더 작다.

따라서 작은 수와 큰 수를 매칭하는 방식이 필요하다.

1 * 4 + 2 * 3 = 10

---

📌 핵심 아이디어

1. 배열 A는 오름차순 정렬

작은 수부터 순서대로 배치한다.

Arrays.sort(A);

---

2. 배열 B도 오름차순 정렬

이후 뒤에서부터 접근하여 내림차순 효과를 만든다.

Arrays.sort(B);

---

3. 가장 작은 수와 가장 큰 수를 곱한다

answer += A[i] * B[B.length - 1 - i];

 

예시

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

계산 큰 수끼리 곱하는 것보다 훨씬 작은 결과를 얻을 수 있다.

1 × 5 = 5
2 × 4 = 8
4 × 4 = 16

합 = 29

---

📌 전체 코드

import java.util.Arrays;

class Solution {
    public int solution(int[] A, int[] B) {

        Arrays.sort(A);
        Arrays.sort(B);

        int answer = 0;

        for (int i = 0; i < A.length; i++) {
            answer += A[i] * B[B.length - 1 - i];
        }

        return answer;
    }
}

 

---

📄 정리

• 최솟값을 만들기 위해서는 작은 수와 큰 수를 매칭해야 한다.
• A는 오름차순 정렬한다.
• B는 오름차순 정렬 후 뒤에서부터 접근한다.
• A[i] * B[n - 1 - i] 방식으로 계산한다.
• 그리디와 정렬을 활용하는 대표적인 문제이다.