[pro] 타겟 넘버

문제 링크

https://programmers.co.kr/learn/courses/30/lessons/43165

참고한 블로그

https://juhi.tistory.com/6
https://velog.io/@ju_h2/Python-프로그래머스-level2-타겟넘버-BFSDFS
https://sexy-developer.tistory.com/40

재귀활용 풀이

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

BFS 풀이

queue에 들어가 있는 건 (idx, 현재까지 계산 결과)

마지막 idx에 도달하면 더이상 idx + 1 하는 것 멈추고 분기를 둬서
중간 결과 값이 target과 동일한지 비교해줌!

위와 같이 else 분기에선 queue에 값이 남지 않을 때까지 계속 max idx에 도달한 계산 결과값들을 popleft() 해서 target과 동일한 값인지 비교해줌 :)

# sol 2.
# BFS 풀이

from collections import deque
def solution(numbers, target):
    answer = 0

    def bfs():
        nonlocal answer
        queue = deque()
        queue.append((0, numbers[0]))
        queue.append((0, -numbers[0]))

        while queue:
            idx, result = queue.popleft()

            if idx < len(numbers) - 1:
                queue.append((idx + 1, result + numbers[idx + 1]))
                queue.append((idx + 1, result - numbers[idx + 1]))
            else:
                # idx가 len(numbers) - 1 이상일 땐 더이상 idx + 1 안 함
                # idx가 max에 달한 것 중 그 결과값만 보는 것!
                # deque엔 idx가 max에 달한 것과 끝까지 계산 시 그 결과값들이 들어있음.
                # 하나씩 queue에서 꺼내서 queue가 없어질 때까지 result == target인지 보는 것
                if result == target:
                    answer += 1
    bfs()

    return answer

stack 활용한 DFS 풀이

# sol 3.
# DFS 풀이
def solution(numbers, target):
    answer = 0

    def dfs():
        nonlocal answer
        stack = [[0, numbers[0]], [0, -numbers[0]]]

        while stack:
            idx, result = stack.pop()

            if idx <= len(numbers) - 2:
                stack.append([idx + 1, result + numbers[idx + 1]])
                stack.append([idx + 1, result - numbers[idx + 1]])
            else:
                if result == target:
                    answer += 1

    dfs()

    return answer