문제
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
Plain Text
복사
사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.
제한 사항
•
주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
•
각 숫자는 1 이상 50 이하인 자연수입니다.
•
타겟 넘버는 1 이상 1000 이하인 자연수입니다.
예시
정답
import numpy as np
def solution(numbers, target):
tree_dict = dict()
tree_dict[0] = np.array([numbers[0]]) # 루트
i = 1 # 트리 높이
while i < len(numbers):
minus_list = tree_dict[i-1] - numbers[i] # 뺀 값 리스트
plus_list = tree_dict[i-1] + numbers[i] # 더한 값 리스트
tree_dict[i] = np.append(minus_list, plus_list) # 트리에 추가
i+=1
possible_list = list(np.append(tree_dict[len(numbers)-1] - 2*numbers[0], tree_dict[len(numbers)-1])) # 리프 노드의 값들
answer = possible_list.count(target) # 개수 구하기
return answer
Python
복사
풀이
•
트리로 풀 수 있는 문제이다.
•
우선 루트 노드에는 numbers의 가장 첫 번째 값을 둔다.
•
그 다음 자식 노드에는 두 번째 값을 뺀 값을 왼쪽 자식 노드로, 더한 값을 오른쪽 자식 노드로 둔다. 그리고 이를 반복하면 맨 마지막에는 총 가능한 경우의 값들이 전부 나온다.
•
4 1 2 1을 예시로 들어보자.
•
4 1 2 1 을 트리로 만들면 다음과 같다.
•
그리고 위의 루트 값은 + 뿐만 아니라 -도 가능하기 때문에 리프 노드의 가능한 값들에서 루트*2를 빼주면 -4를 루트로 했을 때 가능한 값들이 나온다.
•
나의 경우 tree를 dictionary로 만들고 key 값을 트리의 높이로 설정하였다. 그러고 나서 트리를 쌓고 맨 마지막 리프에 있는 값들을 전부 꺼내서 target값과 일치하는 값의 개수를 세었다.
import numpy as np
def solution(numbers, target):
tree_dict = dict()
tree_dict[0] = np.array([numbers[0]]) # 루트
i = 1 # 트리 높이
while i < len(numbers):
minus_list = tree_dict[i-1] - numbers[i] # 뺀 값 리스트
plus_list = tree_dict[i-1] + numbers[i] # 더한 값 리스트
tree_dict[i] = np.append(minus_list, plus_list) # 트리에 추가
i+=1
possible_list = list(np.append(tree_dict[len(numbers)-1] - 2*numbers[0], tree_dict[len(numbers)-1])) # 리프 노드의 값들
answer = possible_list.count(target) # 개수 구하기
return answer
Python
복사
•
numpy를 사용한 이유는 리스트에서 모든 원소들에 일정한 값을 빼고 싶을 때 그냥 리스트는 for문을 써야 하는 번거로움이 있었기 때문.