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

주어진 int[] numbers로 int target 값을 만들수 있는 가짓수를 return 하라

 

sudo code

/*
        sudo code
        dfs bfs를 잘 모르기 때문에 완전 탐색으로 접근
        numbers[0] -> + or -
        2^20 -> 1,048,576 백만이면 많이 안 걸릴듯 가능
        
        1.모든 조합식 때려넣기
        2. target과 비교
        3. 비교시 동일하다면 answer++
        4. return answer
        
        -> 1번 어떻게?
        모든 조합식은 2^length만큼 존재
        ex [1,1,1] => 
        temp = number[0];
        array.add(temp); 1
        array.add(-temp); -1
        temp = number[1];
        arr.get(i-1) + array.add -> 1, -1
        1 1 2 -1 3-> 2 4-> 05-> 06-> -2 7 8
        */

 

recursive
numbers의 길이가 1개가 됐을때 타겟이랑 같은가? 같으면 1을 더한다. 안같으면 0이다
dfs에 필요한 매개변수 sum한 value & numbers & target & numbers.length 대체 값

DFS

class Solution {
    
    int[] numbers;
    int target;
    int answer;
    
    void dfs(int index, int sum){
        // 1. 탈출 조건
        if(index == numbers.length){
            if(sum == target) answer++;
            return;
        }
        
        // 2. 수행동작
        dfs(index + 1, sum + numbers[index]);
        dfs(index + 1, sum - numbers[index]);
    }
    
    public int solution(int[] numbers, int target) {
        answer = 0;
        this.numbers = numbers;
        this.target = target;
        
        dfs(0,0);
        
        return answer;
    }
}

 

BFS

import java.util.*;

class Solution {
    public int solution(int[] numbers, int target) {
        int answer = 0;
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(0); // 초기값은 0으로 시작
        for (int i = 0; i < numbers.length; i++) { // numbers 배열의 모든 요소에 대해 BFS 탐색
            int size = queue.size();
            for (int j = 0; j < size; j++) { // 현재 큐에 들어있는 모든 노드에 대해 BFS 탐색
                int sum = queue.poll(); // 현재 노드의 값을 뽑아냄
                queue.offer(sum + numbers[i]); // 더한 경우 큐에 삽입
                queue.offer(sum - numbers[i]); // 뺀 경우 큐에 삽입
            }
        }
        while (!queue.isEmpty()) { // 큐에 남아있는 모든 노드에 대해 확인
            int result = queue.poll();
            if (result == target) answer++; // 타겟 넘버를 만드는 경우의 수인 경우 카운트
        }
        return answer;
    }
}

 

DP

class Solution {
    public int solution(int[] numbers, int target) {
        int sum = 0;
        for (int i = 0; i < numbers.length; i++) {
            sum += numbers[i];
        }
        // sum보다 target이 크면, target을 만들 수 있는 경우가 없으므로 0을 반환
        if (target > sum) {
            return 0;
        }
        int[][] dp = new int[numbers.length + 1][sum * 2 + 1];
        dp[0][sum] = 1;
        for (int i = 1; i <= numbers.length; i++) {
            for (int j = 0; j < sum * 2 + 1; j++) {
                if (dp[i - 1][j] != 0) { // 이전 위치에서 가능한 경우의 수가 있다면,
                    dp[i][j + numbers[i - 1]] += dp[i - 1][j]; // 다음 위치에서 더한 경우의 수를 더함
                    dp[i][j - numbers[i - 1]] += dp[i - 1][j]; // 다음 위치에서 뺀 경우의 수를 더함
                }
            }
        }
        return dp[numbers.length][target + sum]; // target 넘버를 만드는 경우의 수 반환
    }
}

 

---

참고

 

www.pymoon.com/entry/Programmers-%ED%83%80%EA%B2%9F-%EB%84%98%EB%B2%84-BFSDFS-Java-%ED%92%80%EC%9D%B4?category=929770

 

[Programmers] 타겟 넘버 DFS 풀이, BFS 풀이 (Java)

ChatGpt

https://chat.openai.com/