[프로그래머스 알고리즘] 최솟값 만들기 (Level 2)

문제

과정

두 크기가 같은 배열의 원소를 각각 하나씩 뽑아 곱한 것을 모두 더한 경우의 최소를 구하는 문제이다.
처음에는 모든 수를 곱하는 경우를 구하면 되겠구나 싶어서 배열 A를 모두 뽑는 순열 모두 구하고, 배열 B와 모든 원소를 곱한 합을 구하여 최솟값을 구하려 했다. 따라서 DFS로 A의 순열을 구하는 식으로 알고리즘을 짰다.

import java.util.*;
//
class Solution
{
    public static int min;
//    
    public static void DFS(int[] A, int[] B, int currIdx, boolean[] check, int[] mixArr){
        if(currIdx == A.length){    //섞인 배열과 B를 곱함. 
            int mulSum = 0;
            for(int i = 0; i < B.length; i++){
                mulSum += (mixArr[i] * B[i]);
                // System.out.print(mixArr[i] + " ");
            }
            // System.out.println();
            if(mulSum < min){
                min = mulSum;
            }
        }
        else{
            for(int i = 0; i < A.length; i++){
                if(check[i] == false){
                    check[i] = true;
                    mixArr[currIdx] = A[i];
                    DFS(A, B, currIdx + 1, check, mixArr);
                    check[i] = false;
                }
            }
        }
    }
//    
    public int solution(int []A, int []B)
    {
        int answer = 0;
        boolean[] check = new boolean[A.length];
        int[] mixArr = new int[A.length];
        min = Integer.MAX_VALUE;
//        
        DFS(A, B, 0, check, mixArr);
//        
        answer = min;
//
        return answer;
    }
}

그런데 테스트케이스는 통과하였는데 시간초과가 떴다. 생각해보니 저렇게 순열을 구하면 O(n) = n!의 시간복잡도가 생기는데, 배열의 크기가 1000일 때, 1000! 인 것이므로 비효율적인 알고리즘이었다.

정답

알고보니 너무 간단한 문제였다. 두 배열의 원소를 1:1로 곱한 것의 합의 최소를 구하려면 각 배열에서 가장 큰 값과 가장 작은 값을 곱해주면 되는 것이었다. 따라서, A는 오름차순, B는 내림차순으로 정렬하여 곱하였다.

public int solution(int []A, int []B)
    {
        int answer = 0;
        Integer[] arrB = Arrays.stream(B).boxed().toArray(Integer[]::new);	//primitive타입은 내림차순 안됨. 
        Arrays.sort(A);
        Arrays.sort(arrB, Collections.reverseOrder());
//        
        for(int i = 0; i < A.length; i++){
            answer += A[i] * arrB[i];
        }
//        
        return answer;
    }