[Programmers/Level 2/Java] 최솟값 만들기

Programmers(프로그래머스) 최솟값 만들기

코딩테스트 연습 - 최솟값 만들기

문제 설명

길이가 같은 자연수 배열 A, B가 주어졌을 때, 배열 A와 B에서 각각 한 개의 숫자를 뽑아 두 수를 곱한다.
이러한 과정을 배열의 길이만큼 반복해 누적하여, 최종적으로 최소가 되는 누적 값을 구하라.

예시)
A = [1, 4, 2], B = [5, 4, 4]
0 + 5(1*5) + 16(4*4) + 8(2*4) = 29
answer: 29

---

풀이

한 쪽 배열의 최대값과 다른 쪽 배열의 최소값을 순차적으로 선택하여 곱해 누적하면 최소 누적 값을 구할 수 있다.
즉, 배열 A와 B를 정렬한 다음 배열 A는 오름차순으로, 배열 B는 내림차순으로 곱해 누적하면 된다.

예시)
A = [1, 4, 2] -> [1, 2, 4], B = [5, 4, 4] -> [5, 4, 4]
1*5 + 2*4 + 4*4 = 29

단, 코드로 구현할 때에는 배열 B를 내림차순으로 정렬하기 귀찮아서 배열 A는 정렬된 순으로, 배열 B는 역순으로 순회하며 곱하였다.

import java.util.*;

class Solution
{
    public int solution(int []A, int []B)
    {
        int answer = 0;
        Arrays.sort(A);    // 배열 A 정렬(오름차순)
        Arrays.sort(B);    // 배열 B 정렬(오름차순)
        
        for(int i = 0; i < A.length; i++)
            answer += A[i] * B[B.length-1-i];    // 배열 B는 역순으로 순회하며 계산

        return answer;
    }
}