Programmers / 2단계 / 타겟 넘버 / python

 

코딩테스트 연습 - 타겟 넘버 | 프로그래머스 스쿨 (programmers.co.kr)

 

나의 풀이 

.

 

모범 답안

 

DFS로 구현

def dfs(numbers, target, idx, values):     # idx : 깊이 / values : 더하고 뺄 특정 leaf 값 
    global cnt
    cnt = 0 
	
    if idx == len(numbers) & values == target : # 깊이가 끝까지 닿았으면 
    	cnt += 1
        return 
  
    elif idx == len(numbers) : # 끝까지 탐색했는데 sum이 target과 다르다면 그냥 넘어간다
    	return 
    
    # 재귀함수로 구현 
    dfs(numbers, target, idx+1, values + numbers[idx])   # 새로운 value 값 세팅   
    dfs(numbers, target, idx+1, values - numbers[idx])
 
 def solution(numbers, target) : 
 	
    global cnt
    dfs(numbers, target, 0, 0)
    
    return cnt

 

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 

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

  return count

 

 

[프로그래머스] 타겟 넘버 (python) - BFS/DFS — 다은이의 컴퓨터 공부 (tistory.com)

[프로그래머스] 타겟 넘버 (python) - BFS/DFS