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

programmers.co.kr/learn/courses/30/lessons/12941

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

접근법

- 정렬

 

풀이

첫번째 시도)

재귀로 모든 경우의 수를 전부 탐색해서 풀었지만 시간초과.

 

두번째 시도)

최종 누적함이 최소인 경우는, 최댓값과 최솟값을 더한 경우이다.

따라서 A는 오름차순 정렬, B는 내림차순 정렬을 통해 최소,최대를 더하는 식으로 풀이를 해주었다.

코드

재귀 - (시간초과)

class Solution
{
    static boolean used[];
    static int answer;
    static void dfs(int pos, int A[], int B[], int sum){
        if(sum>answer)
            return;
        if(pos == A.length){
            answer = Math.min(sum, answer);
            return;
        }
        for(int i=0; i<A.length; i++){
            if(!used[i]){
                used[i] = true;
                dfs(pos+1, A, B, sum+(B[i]*A[pos]));
                used[i] = false;
            }
        }
    }
    public int solution(int []A, int []B)
    {
        answer = Integer.MAX_VALUE;        
        used= new boolean[A.length];
        dfs(0 ,A, B, 0);
        return answer;
    }
}

 

정렬 - 옳바른 풀이

import java.util.*;
class Solution
{
    public int solution(int []A, int []B)
    {
        int answer = 0;
        Integer bArr[] = new Integer[A.length];
        for(int i=0; i<A.length; i++){
            bArr[i] = Integer.valueOf(B[i]);
        }
        Arrays.sort(A);
        Arrays.sort(bArr, new Comparator<Integer>(){
            public int compare(Integer o1, Integer o2){
                return -(o1-o2);
            }
        });
        for(int i=0; i<A.length; i++){
            answer += (A[i]*bArr[i]);
        }
        return answer;
    }
}

 

자바 같은 경우 int Array를 내림차순으로 바로 바꾸는 라이브러리는 없는걸로 알고있다.

따라서 한번 Integer타입으로 랩핑을 하고 그것을 람다식으로 내림차순하는 방법을 사용하였다.