프로그래머스 타겟 넘버 BFS

https://school.programmers.co.kr/learn/courses/30/lessons/43165

 

• numbers 원소를 차례대로 앞선 index값에다가 더하거나 빼주면서 큐에 넣는다.
• 더하거나 뺀 값과 index도 튜플 형태로 함께 넣어준다.
• index 끝까지 다 큐에 넣으면 이제 차례대로 popleft하면서 target과 해당 값이 일치하는지 확인한다.

 

from collections import deque

def solution(numbers, target):
    answer = 0
    
    queue = deque()
    queue.append((numbers[0],0))
    queue.append((-numbers[0],0))
    
    while(queue):
        num, i = queue.popleft()
        i += 1
        if i < len(numbers):
            queue.append((num+numbers[i], i))
            queue.append((num-numbers[i], i))
        else:
            if num == target:
                answer += 1
    
    return answer

 

 

• numbers 원소의 양수 값과 음수 값을 튜플 형태로 리스트에 넣어준다.
• product 함수를 통해 cartisian product을 구하고 각 집합의 합을 구한다.
  • l 앞에 *을 붙여주는 이유는 리스트 안 원소를 하나씩 풀어줘야 해서.
  • *연산을 수행하면 리스트 내부의 값들이 가변인자로 변함.

 

• 합과 target값이 동일한 것의 갯수를 return한다.

 

from itertools import product

def solution(numbers, target):
    l = [(x, -x) for x in numbers]
    s = list(map(sum, product(*l)))
    
    return s.count(target)