[파이썬] 프로그래머스 타겟 넘버

프로그래머스

---

나의 풀이

• 기존에 DFS, BFS를 시뮬레이션에서만 활용했어서 간단한 문제임에도 못 풀었다.
• DFS를 활용할 때, 어떤 값을 넘겨줄 지가 정확히 설계하는 것이 중요함을 깨달았다.
• DFS를 재귀, stack 방식 모두를 활용해 구현해봤다.

from collections import deque

def dfs(num_sum: int, idx: int, max_idx: int, numbers: list, target: int):
    global answer
    # DFS 진행 동안 answer 값 증가
    if idx == max_idx:
        if num_sum == target:
            answer += 1
        return
    dfs(num_sum + numbers[idx], idx + 1, max_idx, numbers, target)
    dfs(num_sum - numbers[idx], idx + 1, max_idx, numbers, target)
    # 최종적인 answer 반환
    return answer
            
def solution(numbers, target):
    global answer
    answer = 0
    answer = dfs(0, 0, len(numbers), numbers, target)
    return answer

from collections import deque

def dfs(numbers, target):
    cnt = 0
    
    queue = deque()
    # +, - 시작
    queue.append([numbers[0], 0])
    queue.append([-numbers[0], 0])
    while queue:
        # stack 처리
        val, idx = queue.pop()
        idx += 1
        if idx < len(numbers):
            queue.append([val +numbers[idx], idx])
            queue.append([val -numbers[idx], idx])
        else:
            if val == target:
                cnt += 1    
    return cnt
            
def solution(numbers, target):
    answer = dfs(numbers, target)
    return answer

 

참고