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

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

프로그래머스

 

1. 내가 작성한 풀이

 

재귀 함수를 이용해서 풀었다.

 

1. numbers에 들어있는 숫자를 [+현재 값, -현재 값]으로 나누어 재귀를 돌려줬다.

 

2. 재귀를 반복하며 누적합에 현재 값을 더해준다.

 

3. number를 한 번 다 돌았을 경우 누적합이 target number와 같으면 cnt +=1

 

4. cnt를 return 해주면 된다.

 

cnt = 0

def solution(numbers, target):
    return regression(0,numbers,0,target) #index과 누적합 모두 0으로 시작
    
def regression(now, numbers, now_values, target):    
    global cnt
    if now != (len(numbers)-1): #마지막 number이 아닌 경우
        regression(now+1, numbers, now_values-numbers[now],target) #현재 값 더하고 재귀
        regression(now+1, numbers, now_values+numbers[now],target) #현재 값 빼고 재귀
    else: #마지막 number인 경우
        if (now_values - numbers[now]) == target: #현재 값 더하고 타겟과 같으면 +1
            cnt+=1
        elif now_values + numbers[now] == target: #현재 값 빼고 타겟과 같으면 -1
            cnt+=1
            
    return cnt

 

 

2. BFS 풀이

이걸 BFS로 어떻게 풀 수 있을 지 고민하다가 구글링을 했다.

 

하나하나의 num값들을 현재까지 저장되어있는 모든 누적합에 더해주면 되는 것이었다.

 

간단한 문제였네 세상엔 똑딕이들이 참으로 많다

 

def solution(numbers, target):
    leaves = [0]
    cnt = 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:
            cnt+=1
            
    return cnt