[Algorithm] [Python] Programmers - 타겟 넘버

타겟 넘버

문제 설명

---

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 이하인 자연수입니다.

 

제출코드

---

def solution(numbers, target):
    answer = [0]
    for i in numbers:
        tmp = []
        for j in answer:
            tmp.append(j+i)
            tmp.append(j-i)
        answer = tmp
    return answer.count(target)

 

문제풀이

---

문제는 매우 간단하다.

 

numbers 배열을 순회하며 각각의 원소값을 기존 배열 원소에 더하고 뺀 값을 추가해 나아간다.

 

answer 배열에는 0을 넣어놓고 시작하고, 만일 numbers의 0번째 원소가 1이라면 반복문이 한 턴 진행된 이후 answer는 [1,-1]로 초기화된다.

 

이후 numbers의 1번째 2라면 반복문이 한 턴 진행된 이후 answer에는 기존 배열 원소들에 +2, -2 한 값인 [3, 1, -1, -3]이 들어가게 된다.

 

루트노드 0으로 부터 +,- 연산의 결과값이 포화 이진트리 형태로 자라나게 된다.

 

numbers 배열을 모두 순회한 이후, 결과값이 담긴 리스트에서 count 내장 함수를 이용하여 target 의 개수를 찾아 반환한다.