[python] 타겟 넘버

프로그래머스 타겟 넘버

https://school.programmers.co.kr/learn/courses/30/lessons/43165?language=python3

문제

풀이

#1 내 첫 풀이는 n개씩 +와 -를 리스트에 넣고, itertools.permutations한 후 set 을 써서 모든 결과값을 도출하는 것이었다. -> 당연한 시간 초과

#2 dfs / bfs 를 이용해보기로 한다.

def solution(numbers, target):
  leaves = [0]          # 모든 계산 결과를 담자      
  count = 0 

  for num in numbers : 
    temp = []
	
    # 자손 노드 
    for leaf in leaves : 
      temp.append(leaf + num)    # 더하는 경우 
      temp.append(leaf - num)    # 빼는 경우 

    leaves = temp 

  # 모든 경우의 수 계산 후 target과 같은지 확인 
  for leaf in leaves : 
    if leaf == target : 
      count += 1

  return count

일단 나는 이 코드를 보고, leaves = temp 를 생각하지 못했다. 모든 계산 결과를 담는 리스트가 있어야하고, 더하는 경우, 빼는 경우를 다 리스트에 넣는 거 까진 했는데, 이후에서 막혀서 답지를 봤다. 그랬더니 천재적으로 leaves = temp 로 업데이트 시켜주면서 leaves 안에는 모든 계산 결과만 끝에 남게끔 짰더라... 세상은 넓고 천재는 많다.