[프로그래머스] LV.2 타겟 넘버

[프로그래머스] LV.2 타겟 넘버

 

1. 문제 : Link

정수가 들어있는 배열이 주어지고 해당값의 +- 모든 경우의수의 결과가 target넘버와 같은 경우가 몇가지인지 return하는 알고리즘

 

2. 풀이

1) deque를 이용한 BFS

  1-> (0 or 2) -> (1 or -1) -> (1 or 3) 

2) stack을 이용한 DFS

  1 -> 0 -> -1 

 

3. 코드

1)

from collections import deque
def solution(numbers, target):
    answer = 0
    queue = deque()
    n = len(numbers)
    queue.append([numbers[0],0])
    queue.append([-1*numbers[0],0])
    while queue:
        temp, idx = queue.popleft()
        idx += 1
        if idx < n:
            queue.append([temp+numbers[idx], idx])
            queue.append([temp-numbers[idx], idx])
        else:
            if temp == target:
                answer += 1
    return answer

2)

def solution(numbers, target):
    answer = 0
    queue = [[numbers[0],0], [-1*numbers[0],0]]
    n = len(numbers)
    while queue:
        temp, idx = queue.pop()
        idx += 1
        if idx < n:
            queue.append([temp+numbers[idx], idx])
            queue.append([temp-numbers[idx], idx])
        else:
            if temp == target:
                answer += 1
    return answer

자바 (dfs)

class Solution {
    static int answer = 0;
    
    public int solution(int[] numbers, int target) {        
        int id = 0;
        int len = numbers.length;
        dfs(numbers, +numbers[id], id+1, len, target);
        dfs(numbers, -numbers[id], id+1, len, target);
        return answer;
    }
    
    private  void dfs(int[] numbers, int num, int id, int len, int target){
        if(id < len) {
            dfs(numbers, num+numbers[id], id+1, len, target);
            dfs(numbers, num-numbers[id], id+1, len, target);
        } else{
            if(num == target) answer++;
        }
    }
    
}