[프로그래머스] 타겟넘버(python)

문제 링크 - https://programmers.co.kr/learn/courses/30/lessons/43165

나의 풀이

DFS/BFS로는 도저히 어떻게 풀어야 하는지 감이 안와서 product를 사용해서 풀었다.

from itertools import product
def solution(numbers, target):
    
    a = list(product(['+', '-'], repeat = len(numbers)))
    
    cnt = 0
    for i in a:
        result = 0
        for j in range(len(i)):
            if i[j] == '+':
                result += numbers[j]
            else:
                result -= numbers[j]
        if result == target:
            cnt += 1
    return cnt

BFS를 활용한 풀이

from collections import deque

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

    while queue:
        x, idx = queue.popleft()
        idx += 1
        if idx < n:
            queue.append([x + numbers[idx], idx])
            queue.append([x - numbers[idx], idx])
        else:
            if x == target:
                answer += 1
    return answer

느낀점

• permutations, combinations, product 차이 정확히 알기
• 조합, 순열, 중복 순열은 시간 복잡도가 상당하기 때문에 다른 방법이 있다면 다른 방법으로 풀 수 있게 노력해보기