프로그래머스 - 타겟 넘버

Level 2

문제 설명

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

나의 코드

BFS

from collections import deque


def solution(numbers, target):
    answer = 0
    l = len(numbers)
    queue = deque()
    queue.append([numbers[0], 0])
    queue.append([-1*numbers[0], 0])

    while queue:
        num, index = queue.popleft()
        # print('num: ', num, 'index: ', index)
        index += 1
        if index == l:
            if num == target:
                answer += 1
        else:
            queue.append([num + numbers[index], index])
            queue.append([num + -1*numbers[index], index])
        # print(queue)

    return answer

• 원소값과 인덱스 값을 같이 저장해서 index 값이 list의 길이와 같아질 때까지 +, -의 넓이 만큼 원소를 더해 나간다. 그리고 target 과 같으면 숫자를 세고 아니면 pop을 하면서 확인한다.

DFS

def dfs(numbers, target, dep):
    answer = 0
    l = len(numbers)
    
    if l == dep:
        if sum(numbers) == target:
            return 1
        else: return 0
    else :
        answer += dfs(numbers, target, dep+1)
        numbers[dep] *= -1
        answer += dfs(numbers, target, dep+1)
        return answer

def solution(numbers, target):
    return dfs(numbers, target, 0)

• dfs의 재귀함수로 하나의 원소의 -. + 연산을 depth만큼 재귀호출로 진행한다.

피드백

• 탐색의 원리는 이해했지만 문제에 적용하는 능력이 아직 부족.
• 내 능력으로 다시 한번 풀어보기!!
• 구글링으로 코드 참조함.