[프로그래머스/java] 타겟 넘버

 

https://school.programmers.co.kr/learn/courses/30/lessons/43165

 

---

 

문제풀이1

아이디어

- 모든 경우의 수를 살피기 위해 BFS 방식을 사용한다

- 저장구조는 큐를 사용한다

- 큐에 인덱스와 값을 저장하여 현 단계와 현재까지의 합을 저장한다

코드

import java.util.*;

class Solution {
    public int solution(int[] numbers, int target) {
        int answer = 0;
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{0, 0});
        
        while (!queue.isEmpty()) {
            int[] curr = queue.poll();
            int sum = curr[0];
            int index = curr[1];
            
            if (index == numbers.length){
                if (sum == target) answer++;
            } else {
                queue.add(new int[]{sum+numbers[index], index+1});
                queue.add(new int[]{sum-numbers[index], index+1});  
            } 
        }
        return answer;
    }
}

 

 

시간복잡도

모든 경우의 수를 탐색하므로 O(2^numbers의 길이) -> O(2^n)

 

---

문제풀이2

아이디어

- 모든 경우의 수를 살피기 위해 DFS 방식을 사용한다

- 숫자를 하나씩 추가하면서 현재까지의 합을 저장한다

- 모든 숫자를 사용했을 때, 현재까지의 합 == target이면 answer에 1을 증가시킨다.

코드

class Solution {
    public int solution(int[] numbers, int target) {
        int answer = dfs(numbers, target, 0, 0);
        return answer;
    }
    
    private int dfs(int[] numbers, int target, int index, int sum){
        if (index == numbers.length){
            if (sum == target){
                return 1;
            } else {
                return 0;
            }
        } else {
            return dfs(numbers, target, index+1, sum+numbers[index]) +
            dfs(numbers, target, index+1, sum-numbers[index]);
        }
    }
}

 

시간복잡도

모든 경우의 수를 탐색하므로  O(2^numbers의 길이) -> O(2^n)