[프로그래머스] (LV2) 타겟 넘버

타겟 넘버

JavaScript, Python3

문제 설명

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

입출력 예 설명

문제에 나온 예와 같습니다.

풀이

---

javascript

function solution(numbers, target) {
    var answer = 0;
    var returnArray = []
    
    function calc(i=0,curArray=[]){
        if(i === numbers.length){
            if(curArray.reduce((a,b)=>a+b,0) === target)
                answer++;
            return;
        }
        
        calc(i+1,[numbers[i], ...curArray])
        calc(i+1,[-1*numbers[i], ...curArray])
    }
    calc()
    
    return answer
}

python DFS

def solution(numbers, target):
    n = len(numbers)
    return len([ i for i in range(1<<n) if sum(map(lambda x: [1,-1][int(x[1])]*numbers[x[0]], enumerate(list(bin(i)[2:].zfill(n))))) == target ])

python recursion

def solution(numbers, target):
    if not numbers and target == 0:
        return 1
    elif not numbers:
        return 0
    else:
        return solution(numbers[1:], target - numbers[0]) + solution(numbers[1:], target+numbers[0])

설명

---

DFS 풀이 (javascript, python)

카운트를 세는 방식의 재귀함수 DFS 풀이다.

가장 일반적으로 떠올릴 수 있는 풀이 방법으로, numbers의 길이만큼 재귀함수의 뎁스를 가진다. 매 재귀함수마다 늘어나는 계산은 2가지 (-1을 곱할때와 +1을 곱할때) 이므로 2배씩 늘어난다.

따라서 numbers의 길이가 n 일때 모든 time complexity는

$1 + 2 + 4 + 8 + 2^{n} = \sum_{k=1}^{n} {2^k}$ 이므로 등비수열의 합이 된다.

따라서 이를 계산하면 $2(2^{n}-1)$이 되고, $O(2^n)$을 뜻한다.

DFS + bit_mask (python)

재귀함수 대신 비트마스크를 이용한 반복문으로 풀이하는 방법.

1. i에 1 ~ 1<<n (numbers의 길이 n 만큼의 비트를 가지는 값 / ex: n = 4 ? 1<<n = 16) 까지 반복문을 돌며 값을 할당한다.
2. 할당된 i값을 비트화 한다. n=4 일때, { 0000, 0001, 0010, 0011,   …   , 1111 } 의 값을 가진다.
3. 비트화된 i값을 리스트로 나누어 0일땐 +1을, 1일땐 -1을 곱한뒤 이 값들을 모두 더하고, 더한 값이 target과 같은 것들을 필터링 한다.

비트마스크를 이용한 풀이를 연습하려고 의도적으로 사용했고, 코드를 돌리면 첫 번째 풀이보다도 효율성이 떨어지는 결과를 얻는다.

위 모든 과정에서 최소 $O(nlog_{2}{n})$이 소요되는데, 특히나 3번 과정은 리스트를 나누고 값을 곱한뒤 더하는 계산으로 최소 $O(n^3)$의 복잡도를 보인다. 전체 계산은 대략 $O(n^5log_{2}{n})$이 된다.

여기서 재미있는 점은, 사실 아래 풀이의 효율성이 위 문제보다 좋다는 것이다.

문제에서 주어진 n의 조건은 20 이하다. 이 조건 내에서 위 $O(2^n)$에 접목시키면 대략 100만번의 풀이가 나온다. 아래 식에 20을 접목시키면 대략 2000만번의 풀이가 나온다. 해당 조건에서 아래 풀이가 더 효율성이 떨어지지만, 지수함수와 다항함수의 차이는 그 값이 커질수록 기하급수적으로 차이가 난다.

n의 제한이 40까지만 되도 위 식의 풀이는 1조번 이상의 시간이 소요된다. 그러나 아래식은 대략 10억번의 시간으로 풀이가 가능하다. 풀이 시간 뿐만 아니라 DFS 풀이에서 반복되는 재귀함수의 stack 점유는 제한 조건이 조금만 상향되도 문제로 다가올 것이다.

따라서 이런 점으로 미루어보아, 주어진 문제의 제한사항을 꼼꼼히 확인할 필요가 있다. 특히나 이 문제처럼 다소 가벼운 조건의 문제라면 시간복잡도가 높은 풀이 방법이 오히려 좋은 효율을 보일 수 있기 때문이다.