프로그래머스 - 타겟 넘버

문제

 

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

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

 

 

풀이

 

numbers의 인덱스를 노드로 생각하고, 각 인덱스를 방문할 때마다 인덱스에 해당하는 값을 더한 값과, 뺀 값을 이용해서 dfs, bfs 탐색을 진행한다. 탐색이 끝난 후 중첩한 값과 target을 비교한다.

 

 

코드

 

python - dfs

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

 

def solution(numbers, target):
    answer = 0
    st = []
    st.append([0, numbers[0]])
    st.append([0, -1 * numbers[0]])
 
    while st:
        idx, value = st.pop()
        if idx + 1 == len(numbers):
            if value == target:
                answer += 1
        else:
            st.append([idx + 1, value + numbers[idx + 1]])
            st.append([idx + 1, value - numbers[idx + 1]])
 
    return answer

 

 

python - bfs

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