JavaScript로 네 개의 숫자를 조합해 목표값 만들기

문제 상황

정확히 4개의 숫자로 이루어진 배열 arr을 첫 번째 인수로, 목표값 target을 두 번째 인수로 받는 JavaScript 함수를 작성해야 합니다.

이 함수는 배열에 들어 있는 숫자들을 *, /, +, - 연산자와 괄호 ( )를 적절히 조합했을 때, 그 결과가 target과 같아질 수 있는지 판단해야 합니다.

예를 들어 함수의 입력이 다음과 같다면,

입력

const arr = [5, 3, 2, 1];
const target = 4;

출력

const output = true;

출력 설명

숫자들을 다음과 같이 조합하면 4를 만들 수 있기 때문입니다.

(5 - 1) * (3 - 2) = 4

접근 방법

이 문제는 백트래킹(완전 탐색) 기법으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

1. 배열에서 두 개의 숫자를 선택합니다.
2. 선택한 두 숫자에 가능한 모든 연산(+, -, *, /, 나눗셈은 양방향 포함)을 적용한 결과를 새 값으로 추가하고, 기존 두 숫자는 배열에서 제거합니다.
3. 배열의 길이가 1이 될 때까지 이 과정을 재귀적으로 반복합니다.
4. 마지막에 남은 값이 target과 일치하면 true를 반환합니다.

나눗셈 결과는 소수가 될 수 있으므로, Math.abs(x - target) < 0.0000001처럼 작은 오차 허용 범위를 두고 비교하는 것이 안전합니다.

예제 코드

다음은 전체 구현 코드입니다.

const arr = [5, 3, 2, 1];
const target = 4;
const canOperate = (arr = [], target = 1) => {
   const isValid = x => Math.abs(x - target) < 0.0000001;
   const helper = (arr = []) => {
      if (arr.length === 1) {
         return isValid(arr[0]);
      }
      let valid = false;
      for (let i = 0; i < arr.length; i++) {
         for (let j = i + 1; j < arr.length; j++) {
            const nextArr = arr.filter((x, index) => index !== i && index !== j);
            valid = valid || helper([...nextArr, arr[i] + arr[j]])
            || helper([...nextArr, arr[i] - arr[j]])
            || helper([...nextArr, arr[j] - arr[i]])
            || helper([...nextArr, arr[i] * arr[j]])
            || helper([...nextArr, arr[i] / arr[j]])
            || helper([...nextArr, arr[j] / arr[i]]);
         }
      }
      return valid;
   };
   return helper(arr);
};
console.log(canOperate(arr, target));

출력 결과

true

코드 설명

• isValid: 부동소수점 오차를 고려하여 계산 결과가 target과 일치하는지 확인하는 헬퍼 함수입니다.
• helper: 배열에서 두 숫자를 골라 여섯 가지 연산을 모두 시도하고, 연산 결과를 포함한 새 배열로 재귀 호출을 반복합니다.
• 중간에 한 번이라도 true가 나오면 더 이상 탐색을 진행하지 않고 최종적으로 true를 반환합니다.
• 모든 조합을 탐색했음에도 일치하는 경우가 없다면 false를 반환합니다.