[프로그래머스/Lv. 2] 타겟 넘버 (JAVA)

🔺 문제

프로그래머스

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
class Solution {    
    static int answer = 0;
    
    public int solution(int[] numbers, int target) {
        
        dfs(numbers, target, 0, 0);
        
        return answer;
    }
    
    private static void dfs(int[] numbers, int target, int depth, int sum) {
        if(depth == numbers.length) { // 종료 조건 : 마지막 노드까지 탐색했을 때
            if(target == sum) answer++;
        }
        else {
            dfs(numbers, target, depth + 1, sum + numbers[depth]);  // 해당 노드 값을 더하고 다음 값 탐색
            dfs(numbers, target, depth + 1, sum - numbers[depth]);  // 해당 노드 값을 빼고   다음 값 탐색
        }
    }
}

✅ 해결 아이디어
✔ DFS / BFS
- 탐색할 노드가 남아있는 경우, 이전까지의 노드의 합에서 현재 값을 [더하는  / 빼는] 경우 2가지 경우로 DFS 실행

 

 

---

🔺 다른 풀이들

- BFS를 활용하셨다

import java.util.LinkedList;
import java.util.Queue;

class Solution {
    static Queue<Integer> q = new LinkedList<Integer>();
    public int solution(int[] numbers, int target) {
        int answer = 0;
        
        q.offer(0);
        q.offer(0);
        
        while(q.peek()!=null){
            int level = q.poll();
            int v = q.poll();
            
            if(level == numbers.length){
                if(v == target)
                    answer++;
            }
            else {
                q.offer(level + 1);
                q.offer(v + numbers[level]);

                q.offer(level + 1);
                q.offer(v - numbers[level]);
            }
        }
        return answer;
    }   
}

 

 

- 천재인가..

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

 

---

💬 느낀 점

DFS에서 경우의 수를 이렇게 분리하는 케이스를 잊지 말아야겠다.

이런 정답 형식 코드를 자주 안 풀다 보니까 자꾸 이 코드 형식을 까먹는다

 

1회독	2회독	3회독	4회독	5회독
V	10.12	10.25

 

 

(+ 2회독 10.12)

import java.util.*;
 
class Solution {
    static int[] numbers;
    static int target;
 
    static int cnt = 0;
    
    public int solution(int[] numbers, int target) {
        this.numbers = numbers;
        this.target = target;
        
        dfs(0, 0);  // 뽑은 갯수, 결과
        return cnt;
    }
    
    private static void dfs(int depth, int sum) {
        if(depth == numbers.length) {
            if(target == sum) cnt++;
        }
        else {
            dfs(depth + 1, sum + numbers[depth]);   // 해당 노드 값을 더하고 다음 깊이 탐색
            dfs(depth + 1, sum - numbers[depth]);   // 해당 노드 값을 빼고   다음 깊이 탐색
        }
    }
}

 

 

(+ 10.25 3회독)

import java.util.*;
 
class Solution {
    static int[] numbers;
    static int target;
    static int cnt = 0;
    
    public int solution(int[] numbers, int target) {
        this.numbers = numbers;
        this.target = target;
        
        dfs(0, 0);    // 뽑은 갯수, 결과
        
        return cnt;
    }
    
    private static void dfs(int depth, int sum) {
        if(depth == numbers.length) {
            if(sum == target) {
                cnt++;
            }
            return;
        }
 
        // 현재 숫자를 더한 / 뺀 경우로 나눠 재귀 호출
        dfs(depth + 1, sum + numbers[depth]);
        dfs(depth + 1, sum - numbers[depth]);
 
    }
}

---

(참고)

✔ 풀이 참고

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

 

✔ 그림 설명 이해용

[Java 자바] 프로그래머스> Lv.2 타겟 넘버

[Java] 타겟 넘버 - Lv2 프로그래머스 깊이 우선 탐색(DFS)