문제

[프로그래머스] 최솟값 만들기
https://school.programmers.co.kr/learn/courses/30/lessons/12941

풀이

조건

• 길이가 같은 배열 A, B 두개가 있습니다. 각 배열은 자연수로 이루어져 있다.
• 배열 A, B에서 각각 한 개의 숫자를 뽑아 두 수를 곱한다.
• 곱할 때 사용한 숫자는 다시 사용하지 않는다.

풀이 순서

• List에 배열 A, B의 값을 넣어준다.
• 만들어진 List를 각각 오름차순으로 정렬해준다.
• listA는 앞에서부터, listB는 뒤에서부터 서로 곱해주면 최솟값이 나온다.

코드

import java.util.*;

class Solution
{
    public static int solution(int []A, int []B) {
        int answer = 0;
        
        // 배열 A와 B를 넣어줄 List
        List<Integer> listA = new ArrayList<>();
        List<Integer> listB = new ArrayList<>();
        // List에 값들을 넣어줌
        for(int i=0; i<A.length; i++){
            listA.add(A[i]);
            listB.add(B[i]);
        }
        // 두 List를 각각 정렬해줌(오름차순)
        Collections.sort(listA);
        Collections.sort(listB);

        // listA는 앞에서부터, listB는 뒤에서부터 서로 곱해줌
        for(int i=0; i<listA.size(); i++){
            answer += listA.get(i) * listB.get(listB.size()-1 - i);
        }

        return answer;
    }
}

정리

• 처음에 백트래킹을 사용해서 조합을 구해 풀었더니 시간초과가 났다.
• 더 쉽고 효율적인 방법이 있는지 고민을 먼저 해야겠다.