[프로그래머스][DFS/BFS] 타겟 넘버 - 작성중

문제

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

프로그래머스

 

내 풀이

def solution(numbers, target):
  # 출력: target이 되는 방법의 수

  # 조건: 
  # 2 <= len(numbers) <= 20
  # 1 <= numbers[i] <= 50
  # 1 <= target <= 1000

  # 구현: 
  # 0을 root로 잡고
  # DFS 방식으로 numbers의 각 원소마다 
  # 뺄지, 더할지를 선택해 합하면서 내려가며 
  # 마지막 depth에 도달했을 때 합이 target과 일치한다면 count +1

  # sum을 같이 가져가야 하고
  # depth를 알기 위해 index도 가져가야 함

  # 재귀로 푸는 방법 밖에 일단 생각이 안나서 재귀로 도전
  
  global count
  count = 0
  
  def dfs(numbers, index, sum):
    global count
    if index == len(numbers):
      if sum == target:
        count += 1
      return
    dfs(numbers, index + 1, sum + numbers[index])
    dfs(numbers, index + 1, sum - numbers[index])
  
  dfs(numbers, 0, 0)
  return count

 

내 풀이 개선

def solution(numbers, target):
  def dfs(numbers, index, sum):
    if index == len(numbers):
      if sum == target:
        return 1
      return 0
    return dfs(numbers, index + 1, sum + numbers[index]) + dfs(numbers, index + 1, sum - numbers[index])
    
  return dfs(numbers, 0, 0)

global 변수를 쓰는 것은 가독성도 떨어뜨리고
여러 함수가 존재할 경우 예상치 못한 결과를 초래할 수 있다는 의견을 받았다.

 

의견을 받기 전에도 global count 변수가 별로 좋지 않다고 생각하던중이었어서

어떻게 변경하면 좋을까 방법을 생각하다

 

애초에 count로 집계를 하는게 아니라

dfs 재귀 함수가 sum이 target과 일치할 때만 1을 리턴하도록 하여

모든 dfs의 결과값들이 모아지면 원하는 결과를 얻을 수 있다고 생각해, 위와 같이 변경하였다.

 

그 결과 훨씬 가독성이 좋은 코드로 개선할 수 있었다.

 

다른 풀이 - 리뷰 필요

from collections import deque

def solution(numbers, target):
  answer = 0
  stack = deque([(0, 0)])
  while stack:
    sum, index = stack.pop()
    if index == len(numbers):
      if sum == target:
        answer += 1
    else:
      stack.append((sum + numbers[index], index + 1))
      stack.append((sum - numbers[index], index + 1))
  return answer

위에서 내가 푼 방법들은 DFS를 재귀로 구현했는데

스택과 큐를 사용하는게 메모리 사용에 있어서 더 효율적이라고 알고 있어서

스택과 큐를 사용하는 방법으로도 찾고 찾아 구현해내었다.

 

ㅇㅇ