[프로그래머스] 타겟 넘버

문제 설명

프로그래머스 레벨 2의 문제입니다. (예제가 자바스크립트로 작성되었습니다. 참고부탁드립니다)

 

0과 양의 정수로 이루어진 수 배열이 있을때 이 수들을 모두 더하거나 빼서 특정한 수(타겟 넘버)를 만드는 경우의 수를 찾는 문제입니다.

 

위의 예제를 보면 알 수 있듯 [1, 1, 1, 1, 1]을 통해 3을 만드는 경우의 수는 5가지 입니다.

풀이

function targetNumber(total, numbers, target) {
  if (numbers.length === 0) {
    if (total === target) {
      return 1;
    }

    return 0;
  }

  return targetNumber(numbers[0] + total, numbers.slice(1, numbers.length), target)
    + targetNumber(total - numbers[0], numbers.slice(1, numbers.length), target);
}

function solution(numbers, target) {
  return targetNumber(0, numbers, target)
}

변수, 함수 설명

targetNumber(total, numbers, target): 재귀함수로 모든 경우를 탐색합니다.

간단 설명

 

위의 그림과 같이 작동합니다. targetNumber는 numbers[0]의 값을 더하는 경우, 빼는 경우 두가지로 나뉘어 탐색하고 numbers를 다음에 넣을땐 파이썬 식 표현으로 numbers[1:]과 같이 넣습니다. 즉, 가장 앞 인덱스를 빼고 넣어줍니다.

 

이때 total은 이전까지 연산한 값에서 현재 numbers[0]을 빼거나 더했을때의 값을 의미합니다. 위 그림에서 각각 배열의 값을 제외하고 연산한 값이 됩니다. + 1 - 1, [1, 1, 1]의 경우 + 1 - 1을 계산한 0이 total입니다.

 

종료 조건은 numbers의 길이가 0일때 입니다. 이때 모두 계산한 total이 target(타겟 넘버)와 같다면 1을 반환하여 경우의 수를 증가합니다.