[Level 2] 타겟 넘버

programmers.co.kr/learn/courses/30/lessons/43165#

코딩테스트 연습 - 타겟 넘버

---

접근

타겟넘버를 만들기 위한 연산은 덧셈과 뺄셈 뿐이다. 그래서 각 상황에서 덧셈을 할 때와 뺄셈을 할 때로 나눠서 계산을 해나가고 numbers의 수를 모두 사용했을 때 target과 비교해본다. 

이문제를 dfs와 bfs로 모두 풀어보자

 

구현

▶ DFS

각 상황에서 numbers에 있는 수를 더하거나 빼는 것을 dfs함수를 재귀호출 하여 구현하였다.

result = 0
def dfs(idx, total, numbers, target):
    global result
    if idx == len(numbers):
        if total == target:
            result += 1
        return
    else:
        dfs(idx+1, total+numbers[idx], numbers, target)
        dfs(idx+1, total-numbers[idx], numbers, target)
        
def solution(numbers, target):
    answer = 0
    dfs(0, 0, numbers, target)
    answer = result
    return answer

 

▶ BFS

큐를 활용하여 구현할 수도 있다.

이 문제에서 관건은 덧셈을 하거나 뺄셈을 하거나를 어떻게 구현하는지에 있는 것 같다.

from _collections import deque
def solution(numbers, target):
    answer = 0
    q = deque()
    q.append((numbers[0], 0))
    q.append((-numbers[0], 0))
    while q:
        total, idx = q.popleft()
        idx += 1
        if idx == len(numbers):
            if total == target:
                answer += 1
        else:
            q.append((total+numbers[idx], idx))
            q.append((total-numbers[idx], idx))
    return answer