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

문제

타켓 넘버

프로그래머스

 

방법1. 중복 순열 이용

from itertools import product

def solution(numbers, target):
    # 각 숫자에 대해 + 또는 - 를 선택하는 모든 조합 생성
    cases = list(product(*[(x, -x) for x in numbers]))
    
    # 합이 target인 경우의 개수 반환
    return sum(1 for case in cases if sum(case) == target)

 

데카르트 곱에 관한 내용은 다음 블로그를 참고하시면 됩니다 :) 참고 블로그 

중복순열이 가능한 이유

예시에서 보듯이 1을 여러번 반복해도 되는데 +가 들어간 1과 -가 들어간  1의 경우를 모두 찾아내서 더한 수가 타겟 넘버가 되는지 확인해야 하는 문제입니다. 순서를 신경쓰지 않는다는 점에서 순열이고, 여러번 반복해도 된다는 점에서 중복입니다. product를 사용해서 풀었습니다.

 

방법 2. bfs를 이용

from collections import deque
def solution(numbers, target):
    answer = 0
    q = deque()
    n = len(numbers)
    q.append([numbers[0],0])
    q.append([-1*numbers[0], 0])
    while q:
        tmp, depth = q.popleft()
        depth += 1
        if depth < n:
            q.append([tmp+numbers[depth], depth])
            q.append([tmp-numbers[depth], depth])
        else:
            if tmp == target:
                answer += 1
    return answer