프로그래머스 - 타겟 넘버

문제 설명

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

입출력 예

numberstargetreturn

[1, 1, 1, 1, 1]	3	5
[4, 1, 2, 1]	4	2

입출력 예 설명

입출력 예 #1

문제 예시와 같습니다.

입출력 예 #2

+4+1-2+1 = 4
+4-1+2-1 = 4

• 총 2가지 방법이 있으므로, 2를 return 합니다.

 

 

나의 풀이

def solution(numbers, target):
    dfs = [0]
    idx = 1
    for j, i in enumerate(numbers):
        for _ in range(2**j):
            pre_idx = (idx - 1) // 2
            dfs.append(dfs[pre_idx]+i)
            idx += 1

            pre_idx = (idx - 2) // 2
            dfs.append(dfs[pre_idx]-i)
            idx += 1

    result = dfs[-2**len(numbers):]
    answer = result.count(target)

    return answer

 

나름 BFS로 접근해서 풀려고 해봤다. 하지만 q자료구조를 사용하지 않고 리스트로 풀었는데, DFS, BFS를 좀 더 공부해보고 다음번에 적용을 해봐야겠다. 우선 풀이 알고리즘은 아래와 같다.

 

1) 처음 문제를 보고 0, 4, -4, 5, 3, -3, -5, 7, 3, 5, 1, -1, -5, -3, -7 ....와 같은 트리 구조를 만들고 이를 리스트에 추가를 해야겠다고 생각했다. 그리고 마지막에 추가되는 값들이 각 조합의 결과 값들일 것이고 여기서 타겟 넘버에 해당하는 수만 찾으면 된다고 생각!

 

2) for문 안에 내용을 보면, 부모 노드를 찾고 부모 노드를 기준으로 더한 값, 뺀 값을 구해서 리스트에 어펜드 한다는 의미이다.

 

3) 문제에서 매개변수 (4, 1, 2, 1)의 값이 첫번째 4는 for문 안에 과정(부모 노드에서 더한 값, 뺸값)이 한번, 2번째 1은 위 과정이 2번, 3번째 2는 4번 ...이렇게 이어서 이어진다. 즉 부모 노드의 갯수만큼 해당 과정이 이루어진다. 

 

4) 부모 노드의 갯수만큼 해당 수의 for문(이중)이 도는데, 매개변수의 2**인덱스를 한 값과 같다(2**해당 값의 인덱스 == 부모 노드의 갯수)

 정리를 하면 더하고 빼주는 행위가 부모 노드의 갯수만큼 반복되야함.

 

5) 마지막 결과값은 리스트의 마지막에서 부터 2**len(주어진 리스트의 길이) 그 중에서 타겟넘버의 갯수가 답!