[JAVA/Programmers] 43165 타겟 넘버(자바/프로그래머스)

Programmers 프로그래머스 43165 타겟 넘버 문제는 작업 진도와 속도가 주어졌을 때, 각 배포마다 몇 개의 기능이 배포되는지 구하는 문제이다. 스택/큐 유형의 문제로 난이도는 Level 2이다.

 

Programmers 43165 타겟 넘버 문제 정보

출처

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

알고리즘 분류

- DFS/BFS (깊이 우선 탐색/너비 우선 탐색)

난이도

- Level 2

 

주요 개념

DFS 설명을 위한 그래프

• DFS 알고리즘은 깊이 우선 탐색이라고 하며 그래프의 깊이 부분을 우선적으로 탐색한다.
• 위 그래프에서 0 -> 1 -> 3  -> 4  -> 2  -> 5  -> 6 순으로 탐색하게 된다.
• 재귀(recursive) 기반과 Stack 기반으로 구현할 수 있다.

728x90

문제 풀이 과정

타겟 넘버 그래프

• 사진에서 root를 제외한 + 와 - 로 이루어진 노드들을 DFS로 탐색하며 계산하면 된다.
• 연두색 네모 부분의 그래프를 재귀 함수로 구현한다.
• 각 노드를 방문했을 때 각 level에서의 수는 numbers[level -1] 이고, 부호는 + 또는 - 가 될 것이다.
• sum에 현재 수를 + 한 값과, - 한 값을 누적하고, 다음 +와 - 노드 2가지에서 DFS 수행한다.
• 위 과정을 마지막 level까지 수행한다.
• 마지막 level까지 계산을 완료했을 때 target과 같다면 count 해준다.

반응형

코드 및 설명

public class Solution {

    static int answer;

    public static void main(String[] args) {
        solution(new int[]{1, 1, 1, 1, 1}, 3);  // 5
        solution(new int[]{4, 1, 2, 1}, 4);  // 2
    }

    public static int solution(int[] numbers, int target) {
        answer = 0;
        dfs(numbers, target, 0, 0);
        return answer;
    }

    static void dfs(int[] numbers, int target, int sum, int level) {
        if (level == numbers.length) {
            if (sum == target) {
                answer++;
            }
            return;
        }

        int plusSum = sum + numbers[level];
        int minusSum = sum - numbers[level];
        dfs(numbers, target, plusSum, level + 1);
        dfs(numbers, target, minusSum, level + 1);
    }
}

 

관련 문제

Java로 구현한 DFS/BFS 문제가 아직 없습니다.

---

 

Programmers 프로그래머스 43165 타겟 넘버 문제를 자바 Java로 풀어보았다. 난이도는 Level 2이다.