문제 링크
문제 설명
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을 만드는 방법의 개수를 찾는 문제이다.
문제에서 중요한 단서
순서를 바꾸지 않고 → 순열이 아닌 완전 탐색
숫자의 순서를 바꿀 수 없기 때문에, 각 숫자에 대해
+또는-두 가지 선택지를 탐색해야 함.더하거나 빼서 → 트리 구조 탐색
각 숫자마다
+또는-를 붙이는 이진 트리 형태로 탐색 가능.타겟 넘버를 만들려고 합니다 → 탐색 종료 조건
숫자를 모두 사용한 후, 결과가
target과 같으면 방법의 개수 증가
문제 해결 접근 방법
문제에서 가능한 모든 경우를 고려하면 이진 트리 형태로 확장할 수 있다.
예를 들어, numbers = [4, 1, 2, 1], target = 4가 입력으로 주어진다면:
0
/ \
0 + 4 0 + (-4) → 0번 인덱스 '4' 계산
/ \ / \
4 + 1 4 + (-1) (-4) + 1 (-4) + (-1) → 1번 인덱스 '1' 계산
... → 2,3번 인덱스 계산1단계: 4 추가
- 0에서 → +4
- 0에서 → -4
2단계: 1 추가
- +4에서 → +4 +1 = +5
- +4에서 → +4 -1 = +3
- -4에서 → -4 +1 = -3
- -4에서 → -4 -1 = -5
3단계: 2 추가
- +5에서 → +5 +2 = +7
- +5에서 → +5 -2 = +3
- +3에서 → +3 +2 = +5
- +3에서 → +3 -2 = +1
- -3에서 → -3 +2 = -1
- -3에서 → -3 -2 = -5
- -5에서 → -5 +2 = -3
- -5에서 → -5 -2 = -7
4단계: 1 추가
- +7에서 → +7 +1 = +8
- +7에서 → +7 -1 = +6
- +3에서 → +3 +1 = +4
- +3에서 → +3 -1 = +2
- +5에서 → +5 +1 = +6
- +5에서 → +5 -1 = +4
- +1에서 → +1 +1 = +2
- +1에서 → +1 -1 = 0
- -1에서 → -1 +1 = 0
- -1에서 → -1 -1 = -2
- -5에서 → -5 +1 = -4
- -5에서 → -5 -1 = -6
- -3에서 → -3 +1 = -2
- -3에서 → -3 -1 = -4
- -7에서 → -7 +1 = -6
- -7에서 → -7 -1 = -8각 숫자마다 + 또는 -를 선택하는 두 갈래로 나뉘며, 모든 숫자를 사용했을 때 target과 같은 경우의 개수를 세면 된다.
이 방식으로 모든 경우의 수를 탐색하므로, DFS를 사용하면 간단하게 구현 가능하다.
코드 구현 (Swift)
지금까지 알아본 내용을 코드로 구현하면 다음과 같다.
깊이 우선 탐색(BFS)을 사용하여 모든 경우의 수를 탐색.
index가numbers.count에 도달하면sum == target인지 확인 후 카운트 증가.
func solution(_ numbers: [Int], _ target: Int) -> Int { var count = 0 func dfs(_ index: Int, _ sum: Int) { if index == numbers.count { if sum == target { count += 1 } return } dfs(index + 1, sum + numbers[index]) dfs(index + 1, sum - numbers[index]) } dfs(0, 0) return count }위 코드를 개선하면 다음과 같다.
현재 같은
sum값이 여러 경로에서 반복적으로 계산되고 있음.예를 들어,
(0+4)-1+2-1과(0+4)-1-2+1에서(0+4)-1-2부분은 동일하지만, 여러 경로에서 계산되어 불필요한 연산을 하고 있음.이는 메모이제이션을 사용하여 개선할 수 있음.
func solution(_ numbers: [Int], _ target: Int) -> Int { var memo = [String: Int]() // 메모이제이션을 위한 딕셔너리 생성 func dfs(_ index: Int, _ sum: Int) -> Int { let key = "\(index) \(sum)" // 현재 상태를 저장하기 위한 문자열 key if let cached = memo[key] { return cached // 딕셔너리에 현재 계산하고자하는 값이 존재할 경우 값을 반환 } if index == numbers.count { return sum == target ? 1 : 0 } memo[key] = dfs(index + 1, sum + numbers[index]) + dfs(index + 1, sum - numbers[index]) return memo[key]! } return dfs(0, 0) }너비 우선 탐색(BFS) 사용하면 조금 더 효율적으로 계산할 수 있다.
메모이제이션을 사용하여 중복 연산을 줄였지만, 여전히 같은 depth를 여러번 탐색하고 있음.
BFS는 같은 depth에서 탐색을 끝내면 다음 depth로 넘어가므로 이미 탐색한 경로를 다시 방문하지 않음.
func solution(_ numbers: [Int], _ target: Int) -> Int { var queue: [(Int, Int)] = [(0, 0)] var count = 0 while !queue.isEmpty { let (index, sum) = queue.removeFirst() if index == numbers.count { if sum == target { count += 1 } } else { queue.append((index + 1, sum + numbers[index])) queue.append((index + 1, sum - numbers[index])) } } return count }만약 Swifty한 코드가 좋다면 다음과 같이 작성할 수도 있다.
func solution(_ numbers: [Int], _ target: Int) -> Int { numbers.reduce([0]) { (acc, num) in acc.flatMap { [$0 + num, $0 - num] } }.filter { $0 == target }.count }