[Javascript] 최솟값 만들기 (12941)

문제링크

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

 

접근 방법

두 배열(A,B)의 곱의 합이 최소가 될려면 A의 최솟값과 B의 최대값을 계속해서 곱하면 된다.

처음엔 그냥 마음이 가는대로 풀어보았다.

1. A배열의 최대값과 B배열의 최솟값을 곱하여 answer에 담고

2. A배열과 B배열에서 사용한 최대값고 최솟값을 제거함


하지만 배열의 중간값 제거는 계속해서 index를 새로 할당해야하기 때문에 O(N)으로 비효율적이다.


다시 좋은 방법을 떠올려 A는 오름차순으로 B는 내림차순으로 정렬하고 곱하는 방식으로 풀었다.

 

// 효율 좋은 풀이

function solution(A,B){
    var answer = 0;
    A.sort((a,b) => a - b);
    B.sort((a,b) => b - a);
    
    for(let i = 0; i < A.length; i++){
        answer += A[i] * B[i]
    }

    return answer;
}

// 효율 나쁜 풀이

function solution(A,B){
    var answer = 0;

    while(A.length > 0){
        let aMin = Math.min(...A);
        let bMax = Math.max(...B);
        let aMinIdx = A.indexOf(aMin);
        let bMaxIdx = B.indexOf(bMax);
        answer += aMin * bMax;
        
        A.splice(aMinIdx, 1);
        B.splice(bMaxIdx, 1);
    }

    return answer;
}