[Programmers] 43165 타겟 넘버

안녕하세요. 코테에서 살아남기 기록 시작합니다.

알고리즘 문제를 블로그에 포스팅해도 저작권 상 문제 여부가 궁금했었는데, 프로그래머스 Q&A 페이지를 보니 비상업적, 비영리적 용도로는 괜찮다고 합니다.

백준도 문제 링크를 올리는 식으로 가능하다고 하니 부담없이 올려야겠습니다.

문제

출처: 프로그래머스 코딩 테스트 연습

문제 구성을 먼저 파악했습니다. 시작값 0을 시작으로 배열에 담긴 숫자들이 더해지고 빼집니다. depth 마다 당 2^d 개의 노드를 가지는 트리가 그려지네요.

문제 상단에 힌트도 있습니다. DFS/BFS라고 떡하니 적혀있네요. 부담없이 바로 코드를 작성했습니다.

풀이

function solution(numbers, target) {
  let answer = 0;
  const willVisit = [[0, 0]];

  while (willVisit.length > 0) {
    const [value, depth] = willVisit.shift();

    if (depth === numbers.length && value === target) {
      answer++;
      continue;
    }

    if (depth < numbers.length) {
      willVisit.push([value + numbers[depth], depth + 1]);
      willVisit.push([value - numbers[depth], depth + 1]);
    }
  }

  return answer;
}

자신있게 코드를 제출했는데, 효율성에서 아주 최악이었습니다. 중간중간에 가지치기를 하는 조건들도 넣었지만 그마저도 실패했습니다.

그래서 아예 문제를 생각하는 방식을 바꿨습니다. 이전 노드가 다음 노드에 영향을 주니깐 DP로 풀어볼면 어떨까?

배열을 조작하는 메소드의 호출도 적어지니 왠지 가능할 것 같았습니다.

function solution(numbers, target) {
  const dp = Array.from(Array(numbers.length + 1), () => new Array());

  dp[0] = [0];

  for (let i = 0; i < numbers.length; i++) {
    for (const d of dp[i]) {
      dp[i + 1].push(d + numbers[i]);
      dp[i + 1].push(d - numbers[i]);
    }
  }

  return dp[numbers.length].filter((d) => d === target).length;
}

😀 다행히 성공했습니다. 근데 코드를 쓰던 중 의문이 생겼습니다. 왜 Dynamic Programming이라고 할까? 그래서 조금 찾아보니 제작자가 '그냥 멋있어서 이렇게 지었다.'라고 했다는 말이 있었습니다...

🕶 후기

이번 문제에서 값을 저장하기 위해 2차원 배열을 선언해야 했습니다.

const dp = [];

for (let i = 0; i <= numbers.length; i++) {
	dp.push([]);
}

처음에는 이런 식으로 값을 정했는데 코드가 조금 추해 보입니다.

Array.from 메소드(MDN)

다음 문서를 보면 Array.from()의 인자로 첫 번째는 유사 배열 객체나 iterable 객체, 그리고 두 번째 인자로 mapFn을 넣을 수 있다고 합니다.

const dp = Array.from(Array(numbers.length + 1), () => new Array());

직접 해보니 2차원 배열이 잘 생성됩니다.

DFS 버전

function solution(numbers, target) {
  function DFS(value, depth) {
    if (depth === numbers.length) {
      if (value === target) return 1;
      else return 0;
    } else {
      return (
        DFS(value + numbers[depth], depth + 1) +
        DFS(value - numbers[depth], depth + 1)
      );
    }
  }

  return DFS(0, 0);
}

BFS도 시간 초과가 났으니 당연히 DFS도 시간 초과가 발생할 줄 알았습니다. 그런데 재귀까지 했는데 효율성이 훨씬 뛰어납니다.

배열 접근 메소드와 반복문에서 성능 저하가 발생한 것 같은데 아직 역량이 부족해서 정확한 판단은 못 내리겠습니다.