출처 https://programmers.co.kr/learn/courses/30/lessons/43165?language=python3
Q.
문제 설명
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
나의 풀이
1
처음에는 계산하는 순서도 따져야하는 줄 알고 아래 사진처럼 코드를 작성했다.
재귀를 이용해 dfs를 구현한 코드이다. 탐색하는 순서에 따라 다른 결과로 생각하고 리스트에 넣어줬다. 하지만 numbers에 같은 수가 있는 것을 처리하기 위해 마지막 그래프 결과에서 중복도 제거해주었다.
def solution(numbers, target):
answer = 0
graph = []
prev_elements = []
numbers.extend(list(map(lambda x:x*(-1), numbers)))
def dfs(elements):
if len(elements) == 0:
graph.append(prev_elements[:])
for n in elements:
next_elements = elements[:]
next_elements.remove(n)
next_elements.remove(n*(-1))
prev_elements.append(n)
dfs(next_elements)
prev_elements.pop()
dfs(numbers)
graph = list(set(tuple(map(lambda x:tuple(x), graph))))
for a in graph:
if sum(a) == target:
answer += 1
return answer
이렇게 (1, 2)와 (2, 1) 을 다른 것으로 생각해 2가 return 되었지만 문제에서는 1로 return 되어야 한다는 것을 알게 되었고 위의 코드처럼 굳이 그래프를 구현하지 않고 아래의 풀이처럼 구현했다.
2 (통과)
def solution(numbers, target):
tree = [0]
for i in numbers:
tmp = []
for j in tree:
tmp.append(j+i)
tmp.append(j-i)
tree = tmp
return tree.count(target)어차피 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)def dfs(nums, i, n, t):
ret = 0
if i==len(nums):
if n==t: return 1
else: return 0
ret += dfs(nums, i+1, n+nums[i], t)
ret += dfs(nums, i+1, n-nums[i], t)
return ret
def solution(numbers, target):
answer = dfs(numbers, 0, 0, target)
return answer