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

https://school.programmers.co.kr/learn/courses/30/lessons/43165?language=python3 

프로그래머스

 

내 코드

def solution(numbers, target):
    cnt =0
    arr =[0]
    for i in numbers:
        tmp = []
        for j in arr:
            tmp.append(j + i)
            tmp.append(j - i)
        arr = tmp
    for i in arr:
        if i == target:
            cnt+=1
    return cnt

 

BFS 풀이

트리 유형의 문제라고 생각하면 쉽다.

트리(그래프), 나무위키

코드를 보면 맨 처음 등장하는 for 문의 i = 위 그래프의 레벨이라고 생각하면 쉽다.

그리고 j는 지금까지 더해진 수 = A, B, D 등..

모든 연산 결과는 arr에 저장한다. 그래서 arr 에서 target 과 같은 수를 찾아 카운트한 수가 답이다.

이런 유형의 문제는 어떻게 푸는 것인지 궁금했는데, 이렇게 푸는 것이구나를 깨달았다.

 

다른 사람의 풀이

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)

product를 이용해서 모든 순열의 경우를 구해주었다. 그리고 sum으로 더해준 수 중 count를 통해 target과 같은 수를 찾아내었다.

그리고 *l 하는 이유는 l이라는 리스트 안의 원소들을 하나씩 풀어주어야 product가 가능하기 때문이다.