[Algorithm JavaScript] Level2. 최솟값 만들기

[Algorithm JavaScript] Level2. 최솟값 만들기

Question

Source https://programmers.co.kr/learn/challenge_codes/181

자연수로 이루어진 길이가 같은 수열 A,B 가 있습니다. 최솟값 만들기는 A, B 에서 각각 한 개의 숫자를 뽑아 두 수를 곱한 값을 누적하여 더합니다. 이러한 과정을 수열의 길이만큼 반복하여 최종적으로 누적된 값이 최소가 되도록 만드는 것이 목표입니다.

예를 들어 A = [1, 2] , B = [3, 4] 라면

1. A 에서 1, B 에서 4 를 뽑아 곱하여 더합니다.
2. A 에서 2, B 에서 3 을 뽑아 곱하여 더합니다.

수열의 길이만큼 반복하여 최솟값 10을 얻을 수 있으며, 이 10이 최솟값이 됩니다. 수열 A,B 가 주어질 때, 최솟값을 반환해주는 getMinSum 함수를 완성하세요.

My solution

function getMinSum(A, B) {
  let 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;
}

//아래 코드는 테스트를 위한 출력 코드 입니다.
var tA = [1, 2],
  tB = [3, 4];

console.log(getMinSum(tA, tB));

문제가 이해하기 까다로운 편이다. 길이가 같은 배열에서 각 요소 중 하나씩 빼서 곱한 후를 누적한 값이 최솟값이 되는 알고리즘을 만드는 문제다. 각 배열에서 요소는 하나씩, 한 번씩 활용 가능하다.

문제에 제시되어 있는 로직을 그대로 활용했다. 길이가 같은 배열 A,B 가 있다면 A 배열에서 가장 숫자가 작은 요소와 B 배열에서 가장 큰 숫자를 곱한다. 그리고 A 의 두번째로 작은 수와 B 의 두번째로 큰 수를 곱하고 이전에 곱한 값에 더한다. 이런식으로 배열 끝까지 더해나가면 그 값이 위 문제에서 원하는 최솟값이 된다.

그래서 sort메소드를 활용해 배열 A 는 오름차순으로 나열되도록, 배열 B 는 내림차순으로 나열되도록 만들었다. 그리고 0 부터 배열의 길이 -1 만큼의 index 값 루프를 돌려 두 배열의 각 항을 곱한 후 0 이 대입되어 있는 변수 answer에 더했다. 그럼 만약 배열의 길이가 3 이라면 아래와 같이 반복문이 돌아간다.

(A = [1, 2, 3]), B[(3, 2, 1)](A[0] * B[0]) + A[1] * A[1] + A[2] * B[2];

sort메소드를 통해 곱해야하는 배열의 요소들 순서를 맞췄다. 그 후 공통된 index 값을 활용해 필요한 연산을 했다.