문제:

 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 함수를 작성해주세요.

풀이 방법:

깊이/너비 우선 탐색(DFS/BFS)는 트리 구조를 만드는 것이 핵심이다. 이 문제에서 타겟 넘버를 만드는 방법은 더하거나 빼거나 둘 중 하나다. 따라서 하나의 숫자에 대해 다음 값을 더하는 경우, 빼는 경우로 트리 구조를 만들어 나갈 수 있는 것이다. 첫 수부터 빼는 경우가 있을 수 있으므로 미리 0을 담아 놓고 시작 하도록 한다. 이후 트리를 다 완성 시킨 후 타겟 넘버인 target의 갯수를 카운트 하면 된다.


1
2
3
4
5
6
7
8
9
10
def solution(numbers, target):
    answer_list=[0]
    for i in numbers:
        temporary_list=[]
        for j in answer_list:
            temporary_list.append(j+i)
            temporary_list.append(j-i)
        answer_list=temporary_list
    answer = answer_list.count(target)
    return answer
cs


'Algorithm > Python' 카테고리의 다른 글

[Programmers]Lv 2.가장 큰 정사각형 찾기  (0) 2019.03.02
[Programmers]Lv 3. 입국 심사  (2) 2019.03.01
[Programmers]Lv 3. 정수 삼각형  (0) 2019.02.27
[Programmers]Lv 2. 카펫  (0) 2019.02.26
[Programmers]:Lv 3. 예산  (0) 2019.02.25

+ Recent posts