728x90
반응형
문제:
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 함수를 작성해주세요.
풀이 방법:
깊이/너비 우선 탐색(DFS/BFS)는 트리 구조를 만드는 것이 핵심이다. 이 문제에서 타겟 넘버를 만드는 방법은 더하거나 빼거나 둘 중 하나다. 따라서 하나의 숫자에 대해 다음 값을 더하는 경우, 빼는 경우로 트리 구조를 만들어 나갈 수 있는 것이다. 첫 수부터 빼는 경우가 있을 수 있으므로 미리 0을 담아 놓고 시작 하도록 한다. 이후 트리를 다 완성 시킨 후 타겟 넘버인 target의 갯수를 카운트 하면 된다.
1 2 3 4 5 6 7 8 9 10 | def solution(numbers, target): answer_list=[0] for i in numbers: temporary_list=[] for j in answer_list: temporary_list.append(j+i) temporary_list.append(j-i) answer_list=temporary_list answer = answer_list.count(target) return answer | cs |
728x90
반응형
'Algorithm > Python' 카테고리의 다른 글
| [Programmers]Lv 2.가장 큰 정사각형 찾기 (0) | 2019.03.02 |
|---|---|
| [Programmers]Lv 3. 입국 심사 (2) | 2019.03.01 |
| [Programmers]Lv 3. 정수 삼각형 (0) | 2019.02.27 |
| [Programmers]Lv 2. 카펫 (0) | 2019.02.26 |
| [Programmers]:Lv 3. 예산 (0) | 2019.02.25 |