[Algorithm] Programmers_타겟 넘버 in Java

💡 Programmers Level.2 타켓 넘버:

주어진 배열의 수를 통해 만들 수 있는 숫자 중 타겟 넘버를 만들 수 있는 방법 개수 찾기

🌱 코드 in Java

알고리즘: DFS

import java.util.*;

class Solution {
    int[] nums; // 재귀 함수에 numbers를 계속 복사하지 않도록
    int answer = 0;
    int len;
    
    public int solution(int[] numbers, int target) {
        nums = numbers;
        len = nums.length;
        dfs(0, 0, target);
        return answer;  
    }
    
    public void dfs(int i, int sum, int t) {
        if (i == len) {
            answer = sum == t ? answer + 1 : answer;
            return ;
        }
        dfs(i + 1, sum + nums[i], t);
        dfs(i + 1, sum - nums[i], t);
    }
}

옛날에는 DFS가 진짜 이해가 잘 안되고 어떻게 해야 할 지
감이 안잡혔는데 이번 문제는 기본 중의 기본이기도 했고, 그래서 쉽게 풀 수 있었다.

그런데 왜 BFS가 더 어렵냐... 더 못만들겠어..
BFS문제 좀 많이 풀어봐야겠다.

import java.util.*;

class Solution {
    static class Sum {
        int sum;
        int idx;
        public Sum(int sum, int idx) {
            this.sum = sum;
            this.idx = idx;
        }
    }
    
    public int solution(int[] numbers, int target) {
        int len = numbers.length;
		int answer = 0;
        Queue<Sum> q = new ArrayDeque<>();
        q.add(new Sum(numbers[0], 0)); // +, - 차례로 진행해서 너비 우선 탐색이 될 수 있도록 함
        q.add(new Sum(-numbers[0], 0));
        
        while (!q.isEmpty()) {
            Sum n = q.poll();
            int idx = n.idx + 1;
            if (idx < len) {
                q.add(new Sum(n.sum + numbers[idx], idx)); // 합산을 계속 Q에 넣어서
                q.add(new Sum(n.sum - numbers[idx], idx));
            } else {
                if (n.sum == target) // 모든 숫자를 쓴 합산 결과만 Q에 남고 그들을 검사
                    answer += 1;
            }
        }
        return answer;  
    }
}

BFS 문제를 더 더 더 많이 풀어봐야겠다
아직 잘 감이 안옴

🧠 기억하자

오늘은 무난.