문제 설명
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 이하인 자연수입니다.
접근
아무리 생각해도 이 문제를 어떻게 풀어야 하는지 감이 오지 않는다. 이럴 때 보면 정말 지금까지 해 온 것들이 전부 쓸모없다고 느껴진다.
머리로만 알고 있으면 뭐하나, 직접 사용할 수가 없지 않은가. 개인적으로 이런 순간이 올 때는 나름 스트레스도 받고 씁쓸하기도 한 그런 순간이다.
다른 사람의 해설
[kata][python] 프로그래머스 - 타겟 넘버
이 분의 풀이가 굉장히 잘 적혀 있어서 이분의 풀이를 보고 감을 잡았다. 정답을 보기 보다는 그래도 직접 구현을 해 보고자 하였다.
그렇게 만든 풀이
def solution(numbers, target):
tree = [0 for _ in range(pow(2, len(numbers) + 1))]
answer = 0
def is_leaf_node(idx):
if idx >= pow(2, len(numbers)):
return True
return False
def init_tree(tree, idx, number_idx):
left_node_idx = idx * 2
if not is_leaf_node(idx):
tree[left_node_idx] = numbers[number_idx]
tree[left_node_idx + 1] = -numbers[number_idx]
init_tree(tree, left_node_idx, number_idx + 1)
init_tree(tree, left_node_idx + 1, number_idx + 1)
def preorder_travel(tree, idx, total):
total += tree[idx]
if not is_leaf_node(idx):
preorder_travel(tree, idx * 2, total)
preorder_travel(tree, idx * 2 + 1, total)
else:
if total == target:
nonlocal answer
answer += 1
init_tree(tree, 1, 0)
preorder_travel(tree, 1, 0)
return answer구현 과정
트리 만들기
다른 사람의 해설에 있는 링크에 들어가 해설을 보고 만드는 트리는 반드시 포화 이진 트리로 구성된다.
하나의 부모에 대해 자식이 반드시 2개가 형성되기 때문이다(양수 버전과 음수 버전). 완전 이진 트리라면 배열로 트리를 만드는 것이 효율적일 수 있다.
그래서 배열로 트리를 만들었고, 이때 유의한 점은 numbers의 첫 숫자도 양수 버전과 음수 버전이 있기 때문에 루트 노드는 0으로 설정하기로 했다.
그래서 최대 level은 len(numbers) + 1이 되므로 그 갯수에 맞게 배열을 만든다.
is_leaf_node
트리를 만들 때는 해당 노드가 리프 노드인지 아닌지에 따라 동작이 갈리는 경우가 대다수이기 때문에 반드시 같이 만들어야 한다.
이 경우, 포화 이진 트리이므로 리프 노드는 반드시 같은 레벨에만 존재한다. 따라서 인덱스를 가장 왼쪽에 있는(가장 인덱스 번호가 빠른) 리프 노드의 인덱스 값 이상이라면 True를, 아니라면 False를 반환하게 하면 된다.
init_node
이제 tree의 각 node들에 값을 넣어줘야 한다. 현재 node가 리프 노드가 아니라면 자식 노드의 값을 채워주고, 자식 node로 이동한다.
preorder_travel
트리의 초기화가 끝났다면 만들어진 트리를 순회하여 각 경우별로 합을 더해 target과 같은지 검사해야 한다.
다만, 이 검사는 리프 노드까지 도달했을 때만 해야 한다. 리프 노드 이전에는 아직 모든 수를 더한 것이 아니기 때문이다.
고로 리프 노드가 아니라면 자식 노드들을 대상으로 이 함수를 재귀시키고, 리프 노드라면 검사를 진행한다.
다른 사람의 풀이
def solution(numbers, target):
sup = [0]
for i in numbers:
sub = []
for j in sup:
sub.append(j + i)
sub.append(j - i)
sup = sub
return sup.count(target)[ Programmers ] level 2 - 타겟 넘버 ( python ) - 배우고 정리하기
더했을 때의 합을 리스트에 저장한 후 count 메서드를 통해 정답을 찾는 코드다.
