[프로그래머스] lv2 타겟넘버 / 파이썬, 고득점kit

문제 설명 ==> 타켓 넘버

처음 문제를 읽었을 때 엥? 이게 bfs/dfs 문제라고?? 어떻게 접근하는 거지? 생각이 들었다. 그래프이론 보다는 경우의 수 문제 같은데..

그래서 두번 풀었다. bfs와 python 라이브러리 itertools를 이용해서 ㅎㅎ

방법1) product를 이용

개인적으로 조금 더 끌리는 방법이다. 

from itertools import product
def solution(numbers, target):
    answer = 0
    arr = [ (x, -1*x) for x in numbers ]
    for i in product(*arr):
        if sum(i) == target:
            answer += 1
    return answer

 

코드를 설명하기 앞서 데카르트 곱에 대해 설명하겠다. 데카르트 곱(python에선 itertools에서 product로 사용)은 가능한 모든 조합을 보여준다. 어렵지 않다. 그림을 보면 이해 가능하다. 참고 블로그 

for문에서 *처리를 해준 것은 튜플로 묶혀 있어서 풀어주기 위해서이다.

bfs/dfs문제인데 중복 순열을 써도 되냐고? 이 문제 이외에도 수 많은 다른 그래프이론 문제들이 itertools를 이용해서 풀 수 있고 레퍼런스도 많다. 걱정 마시길!

방법 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

 

코드에 대한 질문이 있으시다면 댓글 또는 쪽지를 보내주면 최선을 다해 답변해 드리겠습니다