[Algorithm] 타켓 넘버 ( 프로그래머스-Level2 / Python )

---

문제 설명

n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.

-1+1+1+1+1 = 3

+1-1+1+1+1 = 3

+1+1-1+1+1 = 3

+1+1+1-1+1 = 3

+1+1+1+1-1 = 3

사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

 

제한사항

• 주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
• 각 숫자는 1 이상 50 이하인 자연수입니다.
• 타겟 넘버는 1 이상 1000 이하인 자연수입니다.

입출력 예

numbers	target	return
[1, 1, 1, 1, 1]	3	5

 

---

나의 코드

1차

answer = 0
tempNumbers = []
tempTarget = 0

def solution(numbers, target):

    global tempNumbers
    tempNumbers = numbers
    global tempTarget
    tempTarget = target

    recurv(numbers[0], 0)
    recurv(-numbers[0], 0)
    
    return answer

def recurv(sum, depth):

    if depth == len(tempNumbers) - 1:
        if sum == tempTarget:
            global answer
            answer += 1
            return
        return
    recurv(sum + tempNumbers[depth+1], depth+1)
    recurv(sum - tempNumbers[depth+1], depth+1)
    
    return

재귀함수를 활용하여 다음 숫자가 빼질때와 더해질 때 두 가지로 계속 분기되도록 코드를 짰다. depth라는 인자를 전달하며 주어진 배열의 갯수에 도달했을 때, target과 같은 숫자이면 answer에 1을 더해줬다. 

2차

answer = 0

def solution(numbers, target):
    
    recurv(numbers[0], 0, target, numbers)
    recurv(-numbers[0], 0, target, numbers)
    
    return answer

def recurv(sum, depth, target, numbers):
    
    if depth == len(numbers) - 1:
        if sum == target:
            global answer
            answer += 1
            return
        return
    
    recurv(sum + numbers[depth+1], depth+1, target, numbers)
    recurv(sum - numbers[depth+1], depth+1, target, numbers)

전역변수 두 개를 재귀함수로 전달함으로써 제거했다. 코드는 간결해졌지만 속도는 아주 조금 느려졌다.

 

프로그래머스 대장답

def solution(numbers, target):
    if not numbers and target == 0 :
        return 1
    elif not numbers:
        return 0
    else:
        return solution(numbers[1:], target-numbers[0]) + solution(numbers[1:], target+numbers[0])

진정한 재귀함수...b