문제

이전에 Python으로 푼 이력이 있어서 이번에는 JavaScript로 풀어보았고,
이전 코드를 다시 보니 DFS로 풀지 않았어서 DFS를 적용하여 한 번 더 풀어보았다.

사실 문제만 봐서는 브루트포스로도 풀 수 있지만, DFS/BFS로 분류가 되어 있어서 의아한 유형이기도 하다!

하지만 유사한 문제에서 백트래킹으로 DFS와 유사하게(재귀) 구성한 적이 있기 때문에 BFS로 푼다!

해설 코드

# Python-브루트포스
def solution(numbers, target):
    resultList = [numbers[0], -numbers[0]]

    for i in range(1, len(numbers)):
        deleteNum = len(resultList)
        for j in range(len(resultList)):
            preNum = resultList[j]
            resultList.append(preNum+numbers[i])
            resultList.append(preNum-numbers[i])

        del resultList[:deleteNum]

    answer = resultList.count(target)
    return answer

# Python-DFS
def solution(numbers, target):
    numberCount = len(numbers)

    global answer
    answer = 0

    def dfs(i, now):
        global answer
        if i == numberCount:
            if now == target:
                answer += 1
        else:
            dfs(i+1, now + numbers[i])
            dfs(i+1, now - numbers[i])

    dfs(1, numbers[0])
    dfs(1, -numbers[0])

    return answer

// Javascript-브루트포스
function solution(numbers, target) {
  var answer = 0;
  possibleNumbers = [];
  numbers.forEach((ele, idx) => {
    if (idx === 0) {
      possibleNumbers.push(ele);
      possibleNumbers.push(-ele);
    } else {
      let prevList = possibleNumbers.slice();
      let newResult = [];
      prevList.forEach((prevEle) => {
        newResult.push(prevEle + ele);
        newResult.push(prevEle - ele);
      });
      possibleNumbers = newResult;
    }
  });
  possibleNumbers.forEach((ele) => {
    if (ele === target) {
      answer += 1;
    }
  });
  return answer;
}

같은 브루트포스이지만 Python에서는 array에서 count 메서드나 슬라이싱이 쉬워서 코드가 짧은 반면에 javascript에서는 그걸 직접 구현해야해서 귀찮았다. 하지만 js 좋아.

답

Python-브루트포스

Python-DFS

결과를 보기 전에는 브루트포스가 DFS보다 느리겠거니 싶었지만은
프로그래머스에서 제공한 테스트케이스에서는 브루트포스가 더 빨랐다.

하지만 메모리가 브루트포스가 더 많이 차지한 것은 확실한 것을 알 수 있었다.

내일은 javascript로 DFS 코드 짜봐야지.