프로그래머스: 타겟 넘버 (DFS)

타겟 넘버

n개의 음이 아닌 정수들이 numbers 배열로 주어질 때, 이 정수들을 순서를 바꾸지 않고 더하거나 빼서 타겟 넘버를 만드는 경우의 수 구하기

제한 조건
2 ≤ n ≤ 20

문제 풀이 조건
각 정수는 1 이상 50 이하인 자연수임.
타겟 넘버는 1 이상 1000 이하인 자연수임.

알고리즘 구상하기

문제 풀이에 집중한다.

문제를 해결해기 위해서는 최대 20개의 정수들을 + 또는 - 로 조합하여 타겟 넘버를 충족하는지 체크해야한다.

각 정수는 +, - 값 둘 중 하나를 갖기 때문에 정수 1개 당 총 2가지의 경우가 생성된다. 결과적으로 2가지 경우의 수를 갖는 정수가 총 20개 존재하므로, 단순히 numbers 배열을 순회하여 문제를 해결한다면 최대 $2^{20}$의 반복이 필요할 것이다. 이 값은 $10^6$ 와 근사하다.

이에 따라 $10^8$ 을 최대로 허용할 수 있는 시간복잡도로 설정했을 때 시간적인 측면보다는 풀이 방법 찾기에 집중했다.

적절한 자료구조: 재귀(DFS)

문제의 핵심은 모든 numbers 배열 요소가 2가지 case를 갖는다는 점이다. 이를 수식으로 바꾸면 $2 × 2 × 2 × 2 …$ 로 나타낼 수 있으며 도식화하면 가지치기 형태로 뻗어나갈 것이다.

이에 따라, 나는 다음과 같이 풀이의 방향을 잡았으며 이를 토대로 ‘재귀’를 이용하여 문제를 풀기로 했다.

1. 동일한 연산을 반복한다.
   특정 index의 값이 양의 정수인가 음의 정수인가에 따라 새롭게 분기가 나누어지고, 다시 이전 index에서 수행한 연산을 반복하도록 한다.

2. 조건을 충족할 때까지 알고리즘을 수행한다.
   ‘타겟 넘버’라는 조건을 충족할 때까지 모든 배열 요소를 방문한다. 조건을 충족하면 즉시 코드 실행을 종료하고 이것이 다른 case의 실행에 영향을 주지 않는다.

문제 풀이 구상하기

numbers 배열의 정수 요소들은 반드시 음 또는 양의 값을 갖는다.

이에 따라 numbers 배열을 순회하여 요소들의 합을 조정한다면, 운좋게 빠른 index에서 타겟 넘버를 충족하더라도 반드시 순회를 마무리 지어 모든 요소에 +, - 값을 부여해야 한다.

가령, [3, 1, 2, 3] 이라는 배열이 존재할 때 타겟 넘버가 ‘3’이라면 0번째 index 값에 +를 부여하면 바로 타겟 넘버를 충족할 수 있다.
그러나 나머지 요소들에도 +, - 값을 부여해야 하며 ‘3’을 유지하기 위해 그 합은 반드시 0이 되도록 조정해야 한다.

이러한 복잡한 조건을 단순화하기 위해 나는 모든 numbers 배열 요소를 기본적으로 양의 정수로 설정하기로 했다.
모든 요소를 양의 정수로 가정하고 선택적으로 음의 정수로 바꾼다면, 특정 index에서 타겟 넘버를 충족했을 때 나머지 요소들의 +,- 여부를 고려하지 않아도 되기 때문이다.
자연스럽게 해당 case에서는 더 이상 순회를 이어갈 필요도 없게 되어 효율성 측면에서 좋다고 생각했다.

위와 같은 결론을 토대로, numbers 배열 요소의 총 합을 default 값으로 설정하고 배열을 순회하며 방문 요소를 음의 정수로 바꾸는 재귀 함수를 만들었다.

함수는 현재 방문하고 있는 index의 요소가 음의 정수인 것으로 가정하고 currentValue에서 해당 값의 2배만큼 빼는 역할을 수행한다. 기존에 양의 정수였던 요소가 음의 정수로 바뀌는 상황이기 때문에 2배만큼 제하도록 설정했다.

함수에는 현재 값을 뜻하는 currentValue 가 target과 일치하는지 체크하는 코드와 currentValue가 target보다 작을 경우 함수 호출을 종료하는 코드를 만들었다.
이는 이전 결과가 target보다 작을 경우, 더 이상 음의 정수로 변경하는 함수를 호출할 이유가 없기 때문이다.

그 결과, 다음과 같은 코드가 완성되었다.

[JavaScript]

function solution(numbers, target) {
  const sumNumber = numbers.reduce((accSum, num) => accSum + num);
  let answer = 0;

  const calculator = (currentValue, currentIndex) => {
    if (currentValue === target) {
      answer += 1;
    } else {
      if (currentValue < target) {
        return;
      }

      for (let i = currentIndex + 1; i <= numbers.length - 1; i += 1) {
        calculator(currentValue - 2 * numbers[i], i);
      }
    }
  };

  calculator(sumNumber, -1);

  return answer;
}