문제
문제설명
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 |
| [4, 1, 2, 1] | 4 | 2 |
입출력 예 설명
입출력 예 #1
문제 예시와 같습니다.
입출력 예 #2
+4+1-2+1 = 4
+4-1+2-1 = 4- 총 2가지 방법이 있으므로, 2를 return 합니다.
풀이
- 연산의 종류는
+,-두 개 - 2 <= 배열의 길이 <= 20
- 시간복잡도는 2^n 이지만 최악의 경우 2^20 이므로 단순 탐색으로도 가능할 듯
Go
DFS 1
func dfs(numbers []int, idx, target, result int) int {
if idx == len(numbers) {
if result == target {
return 1
}
return 0
}
return dfs(numbers, idx+1, target, result+numbers[idx]) + dfs(numbers, idx+1, target, result-numbers[idx])
}
func solution(numbers []int, target int) int {
result := dfs(numbers, 0, target, 0)
return result
} 테스트 1 〉 통과 (8.05ms, 4.22MB)
테스트 2 〉 통과 (7.56ms, 4.23MB)
테스트 3 〉 통과 (0.01ms, 4.23MB)
테스트 4 〉 통과 (0.04ms, 4.14MB)
테스트 5 〉 통과 (0.24ms, 4.22MB)
테스트 6 〉 통과 (0.02ms, 4.22MB)
테스트 7 〉 통과 (0.01ms, 3.56MB)
테스트 8 〉 통과 (0.06ms, 4.15MB)- 재귀를 이용한 일반적인 DFS 풀이 이다.
- 주어진 배열을 인덱스로 탐색하기 때문에 불필요한 카피를 하지 않는다.
DFS 2
func solution(numbers []int, target int) int {
if len(numbers) == 0 {
if target == 0 {
return 1
}
return 0
}
return solution(numbers[1:], target+numbers[0]) + solution(numbers[1:], target-numbers[0])
}테스트 1 〉 통과 (6.45ms, 4.15MB)
테스트 2 〉 통과 (10.64ms, 3.54MB)
테스트 3 〉 통과 (0.01ms, 4.15MB)
테스트 4 〉 통과 (0.04ms, 4.23MB)
테스트 5 〉 통과 (0.30ms, 4.23MB)
테스트 6 〉 통과 (0.01ms, 4.2MB)
테스트 7 〉 통과 (0.01ms, 3.49MB)
테스트 8 〉 통과 (0.10ms, 4.21MB)- 주어진 배열을 슬라이싱해 방문했던 노드를 제외한 새로운 배열을 다음 재귀에 넘긴다.
- 이로인해 DFS 1에서 사용한 인덱싱은 더이상 사용할 필요가 없어진다.
- 재귀함수가 호출될 때 마다 슬라이싱된 배열이 넘어가 메모리 사용량이 늘어날 줄 알았는데 큰 차이가 없었다.
- 찾아보니 Golang의 Slice는 단지 메모리에 대한 포인터일 뿐,
len,cap만 참조하기 때문에 메모리 복사가 일어나지 않는다고 한다. 참고
BFS
func bfs(numbers []int, target int) (count int) {
results := []int{0}
for _, number := range numbers {
temp := []int{}
for _, result := range results {
temp = append(temp, result + number)
temp = append(temp, result - number)
}
results = temp
}
for _, result := range results {
if result == target {
count++
}
}
return
}
func solution(numbers []int, target int) int {
result := bfs(numbers, target)
return result
}테스트 1 〉 통과 (44.28ms, 45.1MB)
테스트 2 〉 통과 (41.78ms, 30.8MB)
테스트 3 〉 통과 (0.02ms, 4.14MB)
테스트 4 〉 통과 (0.19ms, 3.57MB)
테스트 5 〉 통과 (1.50ms, 5.45MB)
테스트 6 〉 통과 (0.07ms, 4.2MB)
테스트 7 〉 통과 (0.03ms, 3.55MB)
테스트 8 〉 통과 (0.32ms, 4.17MB)- 배열의 순서대로 모든 노드를 탐색하는 일반적인 BFS 풀이이다.
- 새로운 슬라이스를 계속해서 생성하기 때문에 메모리 재할당이 반복적으로 일어난다.
Python
DFS 1
def solution(numbers, target):
def dfs(idx, result):
nonlocal numbers
nonlocal target
if idx == len(numbers):
if result == target:
return 1
return 0
return dfs(idx+1, result+numbers[idx]) + dfs(idx+1, result-numbers[idx])
return dfs(0, 0)테스트 1 〉 통과 (385.92ms, 10.2MB)
테스트 2 〉 통과 (426.86ms, 10.2MB)
테스트 3 〉 통과 (0.43ms, 10.1MB)
테스트 4 〉 통과 (1.53ms, 10.2MB)
테스트 5 〉 통과 (11.87ms, 10.3MB)
테스트 6 〉 통과 (0.75ms, 10.3MB)
테스트 7 〉 통과 (0.39ms, 10.1MB)
테스트 8 〉 통과 (3.30ms, 10.1MB)DFS 2
def solution(numbers, target):
if len(numbers) == 0:
if target == 0:
return 1
return 0
return solution(numbers[1:], target+numbers[0]) + solution(numbers[1:], target-numbers[0])테스트 1 〉 통과 (543.72ms, 10.2MB)
테스트 2 〉 통과 (610.07ms, 10.3MB)
테스트 3 〉 통과 (0.69ms, 10.2MB)
테스트 4 〉 통과 (1.82ms, 10.2MB)
테스트 5 〉 통과 (16.54ms, 10.2MB)
테스트 6 〉 통과 (1.05ms, 10.2MB)
테스트 7 〉 통과 (0.51ms, 10.2MB)
테스트 8 〉 통과 (3.63ms, 10.3MB)BFS
def solution(numbers, target):
results = [0]
for number in numbers:
temp = []
for result in results:
temp.append(result+number)
temp.append(result-number)
results = temp
count = 0
for result in results:
if result == target:
count += 1
return count테스트 1 〉 통과 (191.93ms, 50.1MB)
테스트 2 〉 통과 (226.65ms, 49.4MB)
테스트 3 〉 통과 (0.18ms, 10.2MB)
테스트 4 〉 통과 (0.68ms, 10.3MB)
테스트 5 〉 통과 (5.68ms, 11.1MB)
테스트 6 〉 통과 (0.36ms, 10.3MB)
테스트 7 〉 통과 (0.18ms, 10.2MB)
테스트 8 〉 통과 (1.41ms, 10.4MB)Greedy
from itertools import product
def solution(numbers, target):
nodes = [(n, -n) for n in numbers]
results = list(map(sum, product(*nodes)))
return results.count(target)테스트 1 〉 통과 (292.69ms, 34.5MB)
테스트 2 〉 통과 (309.08ms, 34.1MB)
테스트 3 〉 통과 (0.36ms, 10.2MB)
테스트 4 〉 통과 (0.83ms, 10.3MB)
테스트 5 〉 통과 (7.47ms, 10.7MB)
테스트 6 〉 통과 (0.47ms, 10.4MB)
테스트 7 〉 통과 (0.20ms, 10.1MB)
테스트 8 〉 통과 (2.84ms, 10.3MB)- 다른 사람의 풀기에서 본 가장 Python 스러운 풀이 이다.
itertool라이브러리의product를 사용해 모든 경우의 수를 찾고 합한 후 결과와 비교한다.- 완전 탐색은 당연히 타임 에러가 날 줄 알았는데 확실히 프로그래머스가 후한 것 같다.
🖥️