프로그래머스의 타겟 넘버 문제를 함께 풀어보도록 하겠습니다.
문제
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 함수를 작성해주세요.
예제
입력: numbers = [1, 1, 1, 1, 1], target = 3
출력: 5입력: numbers = [4, 1, 2, 1], target = 4
출력: 2풀이 1
3개의 정수가 들었는 배열 [1, 2, 1]가 주어졌을 때, 이 정수들을 더하거나 뺄 수 있는 모든 방법을 따져보겠습니다.
+1 +2 +1
+1 +2 -1
+1 -2 +1
+1 -2 -1
-1 +2 +1
-1 +2 -1
-1 -2 +1
-1 -2 -1그럼 이렇게 8개 수식을 얻을 수 있는데요. 이 중에서 계산 결과가 주어진 타겟 너버와 동일한 수식을 세면 우리가 찾고자 하는 정답이 될 것입니다.
그럼 주어진 정수들로 만들 수 있는 모든 수식을 어떻게 만들어 낼 수 있을까요? 바로 재귀 알고리즘을 사용하면 되는데요. 재귀 호출의 매 단계 마다 배열의 인덱스가 1씩 증가시키면서, 각 정수에 대해서 덧셈과 뺄셈, 이렇게 두 번의 연산을 수행하면 되겠습니다.
재귀 함수의 인자로 현재 인덱스와 이전 인덱스까지 누적 계산 결과를 받으면, 다음 인덱스와 현재 정수의 숫자를 더한 값과 뺀 값을 가지고 다시 재귀 함수를 호출할 수 있을 것입니다.
현재 인덱스가 배열의 길이와 동일할 때까지 재귀 함수의 호출은 멈춰야 하며, 이 때 누적 계산 결과가 타겟 넘버와 동일하다면 개수를 증가 시키면 됩니다.
그럼 지금까지 설명다른 알고리즘을 파이썬으로 짜보겠습니다.
def solution(numbers, target):
count = 0
def dfs(idx, total):
nonlocal count
if idx == len(numbers):
if total == target:
count += 1
return
dfs(idx + 1, total + numbers[idx])
dfs(idx + 1, total - numbers[idx])
dfs(0, 0)
return count동일한 코드를 자바스크립트로도 짜보겠습니다.
function solution(numbers, target) {
let count = 0;
function dfs(idx, total) {
if (idx === numbers.length) {
if (total === target) {
count++;
}
return;
}
dfs(idx + 1, total + numbers[idx]);
dfs(idx + 1, total - numbers[idx]);
}
dfs(0, 0);
return count;
}이해를 돕기 위해서 [1, 2, 1]이 배열로 주어졌을 때 이 재귀 알고리즘의 어떻게 실행되는지 한번 시각화해보았는데요.
만약에 타겟 넘버가 2라면 우리는 2개의 방법을 찾을 수 있을 것입니다.
+1 = 1
1 + 2 = 3
1 + 2 + 1 = 4
1 + 2 - 1 = 2 ✅
1 - 2 = -1
1 - 2 + 1 = 0
1 - 2 - 1 = -2
-1 = -1
-1 + 2 = 1
-1 + 2 + 1 = 2 ✅
-1 + 2 - 1 = 0
-1 - 2 = -3
-1 - 2 + 1 = -2
-1 - 2 - 1 = -4n을 주어진 배열의 길이라고 했을 때, 이 풀이의 시간 복잡도는 O(2^n)인데요.
재귀 함수를 한 번 호출할 때마다 두 번의 연쇄 호출이 일어나기 때문입니다.
호출 스택의 깊이는 n과 비례하므로 공간 복잡도는 O(n)이 되겠습니다.
재귀 함수 내에서
nonlocal키워드를 사용하는 이유에 대해서는 관련 포스팅을 참고하세요.
풀이 2
만약에 면접관이 스택 오버플로우(Stack Overflow) 문제 때문에 재귀 알고리즘을 별로 좋아하지 않는다면 어떻게 해야 할까요?
이럴 때는 스택(Stack) 자료구조를 사용하여 반복 알고리즘으로 구현하면 됩니다.
스택에 최초에는 인덱스와 누적 값의 쌍을 (0, 0)으로 초기화하여 추가하고, 스택에 아무것도 남지 않을 때까지 반복을 해야 합니다.
각 단계에서 스택에서 인덱스와 누적 값을 꺼내서, 다음 인덱스와 누적 값에 현재 정수를 더한 값의 쌍과 현재 정수를 뺀 값의 쌍을 추가합니다.
만약에 인덱스가 배열의 길이와 동일하다면, 누적 값이 타겟 넘버와 같은지 확인해서 같다면 1을 더해주고, 반복문을 건너뜁니다.
def solution(numbers, target):
count = 0
stack = [(0, 0)]
while stack:
idx, total = stack.pop()
if idx == len(numbers):
if total == target:
count += 1
continue
stack.append((idx + 1, total + numbers[idx]))
stack.append((idx + 1, total - numbers[idx]))
return count이번에는 자바스크립트로 동일한 코드를 짜볼께요.
function solution(numbers, target) {
let count = 0;
let stack = [[0, 0]];
while (stack.length > 0) {
const [idx, total] = stack.pop();
if (idx === numbers.length) {
if (total === target) {
count++;
}
continue;
}
stack.push([idx + 1, total + numbers[idx]]);
stack.push([idx + 1, total - numbers[idx]]);
}
return count;
}참고로 배열로 [1, 2, 1]이 주어지고, 타겟 넘버가 2라면, 스택에 저장된 인덱스와 누적 값의 쌍은 시간에 따라 아래와 같이 바뀌게 될 것입니다.
[(0, 0)]
[(1, 1), (1, -1)]
[(1, 1), (2, 1), (2, -3)]
[(1, 1), (2, 1), (3, -2), (3, -4)]
[(1, 1), (2, 1), (3, -2)]
[(1, 1), (2, 1)]
[(1, 1), (3, 2), (3, 0)]
[(1, 1), (3, 2)] ✅
[(1, 1)]
[(2, 3), (2, -1)]
[(2, 3), (3, 0), (3, -2)]
[(2, 3), (3, 0)]
[(2, 3)]
[(3, 4), (3, 2)] ✅
[(3, 4)]이 반복 알고리즘의 복잡도는 이전 재귀 알고리즘과 동일한데요.
스택의 메모리 사용량은 n과 비례하고, 연산량은 여전히 매 단계에서 2배씩 증가하기 때문입니다.