[Lv.2] 타겟 넘버 : Java

프로그래머스

 

 

 

이해하기

처음 떠오른 아이디어는 dfs 사용 + (+, -) 부호 사용이었지만, 어떻게 구현을 해야할지 전~혀 감이 안 잡혔다.

 

아래 블로그글 참고!

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

 

부호 변경을 도대체 어떻게 해야할까 고민했는데, 이 분이 너무나 쉽게 푸셔서 조금 허탈해진🫥

1. dfs 사용
2. 마지막 노드까지 탐색했들 때 타겟 넘버와 결과값이 같으면 정답 카운트 증가
3. 탐색할 노드가 남아있는 경우 이전 노드까지의 합에서 현재 노드값을 더하고(+ 부호) 빼는(- 부호) 두 가지 경우로 dfs 재실행

+ 부호, - 부호를 따로 구현하는 것이 아니라!! dfs에서 파라미터를 넘겨줄 때의 값만 다르게하면 두 가지 경우를 다 구할 수 있다는 것...!

(이런 간단한 접근 방법이 있었다니🥹)

 

 

문제풀이

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

    public void dfs(int[] numbers, int depth, int target, int sum) {
        if (depth == numbers.length) {
            if (target == sum) {
                answer++;
            }
        } else {
            dfs(numbers, depth + 1, target, sum + numbers[depth]);
            dfs(numbers, depth + 1, target, sum - numbers[depth]);
        }
    }
}

 

    int answer = 0;

 

카운팅해줄 answer 전역 변수 선언!

 

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

 

dfs의 첫번째 파라미터로는 numbers와 depth = 0, target, sum = 0

 

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

 

만약 depth가 numbers의 길이와 같아진다면 (끝까지 탐색했다면)

타겟 넘버와 sum을 비교하여 같다면 answer++ 아니라면 pass

 

        } else {
            dfs(numbers, depth + 1, target, sum + numbers[depth]);
            dfs(numbers, depth + 1, target, sum - numbers[depth]);
        }

 

아직 끝까지 가지 못했다면 dfs 두 가지 실행!!

1. sum에 numbers[depth]를 더해준 것
2. sum에 numbers[depth]를 빼준 것

이 부분에서 너무 쉬워서 이게 된다고...? 싶었다 ㅜㅅㅜ

 

 

 

 

쉽고 간단하고... 심지어 짧은! 코드지만 항상 아이디어 떠올리는 것이 어렵다.