[Java] 프로그래머스 - 최솟값 만들기

초기 코드

import java.util.*;

class Solution
{
    private int answer=Integer.MAX_VALUE;
    private int[] A;
    private int[] B;
    //사용된 인덱스를 저장
    private List<Integer> usedA = new ArrayList<>();
    private List<Integer> usedB = new ArrayList<>();
    
    public int solution(int[] _A, int[] _B)
    {
        A = _A;
        B = _B;
        dfs(1, A.length, 0);
        
        return answer;
    }
    
    private void dfs(int currentDepth, int maxDepth, int sum){
        if(currentDepth>maxDepth){
            answer = Math.min(answer, sum);
            return;
        }
        
        if(sum>=answer){
            return;
        }
        
        for(int a=0; a < A.length; a++){
            //개선할 코드
            if(usedA.contains(a)){
                continue;
            }
            //
            usedA.add(a);
            
            for(int b=0; b < B.length; b++){
                
                //개선할 코드
                if(usedB.contains(b)){
                    continue;
                }
                usedB.add(b);
                //개선할 코드
                dfs(currentDepth+1, maxDepth, sum+A[a]*B[b]);
                usedB.remove(usedB.size()-1);
            }
            usedA.remove(usedA.size()-1);
        }
    }
}

 

DFS를 완전탐색으로 풀었으나, \(O(N^4)\)의 시간 복잡도 발생.

 

이후 개선할 방법을 찾다가 훨씬 더 간단한 아이디어를 생각하게 되었다.

 

A, B배열의 각 요소끼리의 곱을 합산한 최솟값은 두 배열을 각각 내림차순과 오름차순으로 정렬한 뒤 0번 인덱스부터 곱해주면 정렬 시간복잡도 + \(O(N)\)만으로 문제해결이 가능한 것이었다.

 

개선한 코드

import java.util.Arrays;
import java.util.Collections;
import java.util.stream.*;


class Solution
{
    public int solution(int []A, int []B)
    {
        Integer[] _A = Arrays.stream(A).boxed().toArray(Integer[]::new);
        int answer = 0;
        
        //1) A정렬, B정렬
        Arrays.sort(_A, Collections.reverseOrder());
        Arrays.sort(B);
        
        //2) A의 크기 만큼 돌면서 돌면서 각 자연수 곱  + 합산
        for(int i=0; i<_A.length; i++){
            answer+=_A[i]*B[i];
        }
        
        return answer;
    }
}

 

그러나 위 문제는 효율성도 배점이 들어가는 문제로 시간초과가 발생하게 되었다. 개인적으로 이런 채점기준을 채택한 프로그래머스가 유별나다고 생각하지만 질문하기를 통해 더 나은 코드를 찾아보았다.

 

정답 코드

import java.util.*;

class Solution
{
    public int solution(int []A, int []B)
    {
        int answer = 0;
        
        PriorityQueue<Integer> _A = new PriorityQueue<>(Collections.reverseOrder());
        PriorityQueue<Integer> _B = new PriorityQueue<>();
        
        for(int i=0; i<A.length; i++){
            _A.add(A[i]);
            _B.add(B[i]);
        }

        while(!_A.isEmpty()){
            answer+=_A.poll()*_B.poll();
        }
        
        return answer;
    }
}

 

두 배열의 요소를 내림차순의 PriorityQueue와 오름차순의 PriorityQueue에 삽입해서 해결하면 더 효율적으로 풀 수 있다는 아이디어이다.