[프로그래머스] 타겟 넘버 (Python)

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

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

참고

https://hkim-data.tistory.com/31?category=1016184 

#2-3 Python 코딩테스트 그리디 알고리즘 , DFS & BFS

DFS 풀이는 재귀를 사용하거나 스택(리스트)를 활용하면 된다

BFS 풀이는 큐 자료구조를 활용하면 된다.

 

이 문제는 숫자가 주어질 때 그 부호를 +로 하느냐 -로 할떄의 모든 경우를 정해주면 된다.

이를 DFS BFS를 통해 풀면 된다.

 

DFS (재귀 풀이)

answer = 0
def dfs_recursive(idx,numbers,target,value):
    global answer
    n = len(numbers)
    if n == idx and target == value:
        answer += 1
        return
    elif n == idx:
        return
    else:
        dfs_recursive(idx+1,numbers,target,value+numbers[idx])
        dfs_recursive(idx+1,numbers,target,value-numbers[idx])

def solution(numbers, target):
    global answer
    dfs_recursive(0,numbers,target,0)
    return answer

 

DFS (리스트 활용)

def solution(numbers, target):
    arr = [0]
    for i in numbers:
        temp =[]
        for j in arr:
            temp.append(j+i)
            temp.append(j-i)
        arr = temp[:]
    return arr.count(target)

 

BFS (deque 활용!)

from collections import deque
def solution(numbers, target):
    answer = 0
    queue = deque()
    queue.append((0,0))
    while queue:
        i, value = queue.popleft()
        if i == len(numbers) and value == target:
            answer +=1
        elif  i == len(numbers):
            pass
        else:
            queue.append((i+1,value + numbers[i]))
            queue.append((i+1,value - numbers[i]))
    return answer