[python/dfs, bfs] 32. 타겟 넘버(feat. product 함수) ★

문제 출처

programmers.co.kr/learn/courses/30/lessons/43165

코딩테스트 연습 - 타겟 넘버

 

문제 설명

n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

 

제한사항

- 주어지는 숫자의 개수는 2개 이상 20개 이하입니다.

- 각 숫자는 1 이상 50 이하인 자연수입니다.

- 타겟 넘버는 1 이상 1000 이하인 자연수입니다.

 

입출력 예

numbers	target	return
[1, 1, 1, 1, 1]	3	5

 

---

 

bfs, dfs는 아직 친해지지 못해서 코드를 거의 작성하지 못했다. 다른 사람들의 풀이를 보면서 공부하고 다음번에는 스스로 짜보자!

 

다른 사람의 풀이-1

answer = 0

def dfs(idx, numbers, target, value):
    global answer
    N = len(numbers)
    if (idx == N and target == value):
        answer += 1
        return
    if (idx == N):
        return
    
    dfs(idx+1, numbers, target, value + numbers[idx])
    dfs(idx+1, numbers, target, value - numbers[idx])

def solution(numbers, target):
    global answer
    dfs(0, numbers, target, 0)
    return answer

numbers, target 인자 외에도 idx, value 인자를 추가해서 재귀형태로 작성해주었다.

 

 

다른 사람의 풀이-2

def solution(numbers, target):
    if not numbers and target == 0 :
        return 1
    elif not numbers:
        return 0
    else:
        return solution(numbers[1:], target-numbers[0]) + solution(numbers[1:], target+numbers[0])

1번 코드와 비슷한 논리인데 차이점을 찾아보자면,

1) ind, value 인자 대신 numbers, target 인자에서 numbers의 첫 값을 빼주는 방식으로 작성했다.

2) answer 인자를 따로 설정하지 않고도 +를 사용해서 알아서 카운트가 되도록 설정했다.

 

다른 사람의 풀이-3

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

위 코드를 나눠서 생각해보았다.

 

1) [(x, -x) for x in numbers]

2)-1 list(product(*l))

요렇게 출력이 된다. 이해가 잘 되지 않아서 product의 다른 예시를 살펴보았다.

 

* itertools.product 함수 예시(출처: programmers.co.kr/learn/courses/4008/lessons/12835)

 

2)-2 list(map(sum, product(*l)))

각 튜플의 sum을 구해주는 공식이다. 그럼 [5, 3, 3, 1, 3, 1, 1, ...] 이런 결과를 얻을 수 있다.