target number 문제 풀이

see also : https://programmers.co.kr/learn/courses/30/lessons/43165?language=javascript

이해

for문을 이용해 모든 경우를 다 탐색한다면 시간초과가 날 것으로 보인다. 이런 종류의 bfs, dfs는 참 어렵게 느껴진다. 최단 경로 검색과 같이 맵 하나 주고 탐색하는게 왠지 모르겠지만 더 쉽게 느껴진다.

계획

이 문제를 처음 접했을 때 dfs 가 생각이 났다. 재귀를 이용한 dfs로 모든 경우에 대해 식을 계산하여 산출한 결과값이 target 과 같다면 전역 변수로 count 값을 증가시켰다. 하지만 테스트케이스 1,2 번에서 시간 초과가 발생했고, 전역변수를 사용했다는 사실도 마음에 들지 않았다.

이 문제도 어떠한 메모이제이션 기법이 필요한게 아닐까 생각이 들었다. 입력값 [1, 2, 3, 4, 5] 에 대해서 모든 경우를 손으로 써 보면서 어떠한 해답이 보이기 시작했다.

그래서 최근 코딩테스트에서 사용했던 bfs를 적용해보기로 했다.

실행

const bfs = (numbers, target) => {
  const queue = [], answer = [];
  
  let len = numbers.length - 1;
  let front = 0, index = 1, current = numbers[0];

  while (len--) {
    let repeat = Math.pow(2, index) / 2;
    while (repeat--) {
      queue.push(...[current + numbers[index], current - numbers[index]]);
      if (!len) {
        answer.push(...[current + numbers[index], current - numbers[index]]);
      }
      current = queue[front++];
    }
    index += 1;
  }

  return answer.reduce((acc, value) => 
    Math.abs(value) === target ? acc + 1 : acc, 0
  );
}

const solution = (numbers, target) => bfs(numbers, target);

• queue 는 이전까지 더한 숫자의 결과가 담겨있는 배열이다.
• 하나의 숫자당 두 가지 경우의 수가 존재하므로 repeat 는 2의 index 제곱만큼 필요하며, 한 번 추가할 때 두개의 수를 추가하므로 2로 나눈 반복 횟수를 가진다.
• 이 과정을 반복하며 queue에 숫자를 넣다가 len이 0이 되면 그 때는 위 그림의 빨간 줄에 해당하는 최종 연산 결과이다. 이 결과는 answer 배열에 담는다.
• answer 배열에서 원소의 절댓값이 target과 같으면 target number를 찾은 것이므로 1 증가시키고 아니면 증가시키지 않도록 하여 결과를 반환한다.

반성

• 풀이를 생각해내는데 오랜 시간이 걸렸다. 코딩테스트에서 나왔다면 못 풀었을 것이다.
• 오랜만에 bfs를 하니 코드를 구현하는게 어려웠다. 역시 꾸준함이 답이구나...
• 다른 사람의 풀이에서 dfs로 더 빠르게 푼 사람이 있었다. 이건 다음에 다시 풀면서 이 풀이로 다시 풀어봐야겠다.