[프로그래머스] Lv. 2 타겟 넘버

Python3, DFS/BFS

문제

제한 사항

입출력 예시

나의 풀이 (시도)

• 반복문을 돌면서 numbers 배열 인덱스값들을 더하고 뺀 후 스택(tmp)에 저장한다
• 스택에 있는 값이 target 값과 같다면 count(아래 코드에서는 answer) 값을 1 증가시킨다

주요 포인트

bfs/dfs 풀이인 이유

numbers가 [1, 1, 1, 1, 1] 일 때,
1은 2나 0이 될 수 있다(1+1=2 or 1-1=0)
현재 tmp: [1, 2, 0] (1은 pop)
다음은 [2, 0, -1, 1] (2를 pop하고 가질 수 있는 값)
이렇게 하나씩 계산해 보면서 target과 스택에 있는 값이 같아지면 answer + 1을 해준다

최종 코드

# bfs
def solution(numbers, target):
    answer = 0
    stack = [0]
    
    for i in numbers:
        tmp = []
        for j in stack:
            tmp.append(j + i)
            tmp.append(j - i)
        stack = tmp
        
    for s in stack:
        if s == target:
            answer += 1
    return answer