[문제]

n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

제한사항

• 주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
• 각 숫자는 1 이상 50 이하인 자연수입니다.
• 타겟 넘버는 1 이상 1000 이하인 자연수입니다.

입출력 예

입출력 예 설명
문제에 나온 예와 같습니다.

[풀이]

function solution(numbers, target) {
  let answer = 0;
  const forLength = Math.pow(2, numbers.length);
  const calLength = numbers.length;
  let signNum = '';

  for(let i = 0; i < forLength; i++) {
    signNum = (Math.pow(2, calLength) - (1 + i)).toString(2).padStart(numbers.length, '0');
    let evalStr = '';

    for(let j = 0; j < calLength; j++) {
      evalStr += ((signNum[j] === '1' ? '+' : '-') + numbers[j]);
    }
   
    (eval(evalStr) === target) && (answer += 1);
  }

  return answer;
}

부호가 +, - 둘 중 하나니까 각 숫자의 부호를 2진법으로 계산함.
2의 numbers.length제곱 만큼 경우의 수가 필요함.
31부터 2진법으로 치환하고, 그 값이 11111이니까 1일 때는 +로 바꿔서 숫자들을 계산함.
1씩 감소하면서 00000이 될때까지 같은 방법으로 0일 때는 -로 바꿔서 계산함.

위 방법으로 하면 아래처럼 나옴
ex) +1+1+1+1+1, +1+1+1+1-1, +1+1+1-1+1, +1+1+1-1-1, ...

계속 반복하면서 연산 값이 target이랑 같을 때만 answer를 증가시킴.

살짝 코드 수정

function solution(numbers, target) {
  let answer = 0;
  const calLength = numbers.length;
  const forLength = Math.pow(2, calLength);
  let signNum = '';

  for(let i = 0; i < forLength; i++) {
    signNum = (forLength - (1 + i)).toString(2).padStart(calLength, '0');
    let evalStr = '';

    for(let j = 0; j < calLength; j++) {
      evalStr += ((signNum[j]|0 ? '+' : '-') + numbers[j]);
    }

    (eval(evalStr) === target) && (answer += 1);
  }

  return answer;
}