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

문제

---

풀이 (2021.01.03)

처음에는 여태 백준문제 풀면서 했던 것처럼 그래프를 만들어서 탐색해야하나 고민했는데, 어떻게 그래프를 생성해야 할지도 감이 안 잡혀서 그냥 배열 안에서 탐색하는 방식으로 구현해보려다가 성공했다. 희희

알고리즘 문제 풀 때 너무 전형적인 풀이에 사로잡히지 말고, 백지 상태에서 어떻게 접근해서 풀면 좋을지 스스로 생각해내는 게 중요한 것 같다. 내가 생각해낸 방법은 기본적으로 아래와 같다.

• numbers 배열을 순차적으로 탐색하면서 2가지 경우로 분기한다.
• numbers 배열의 끝에 도달했을 때의 result를 target과 비교해서 count를 증가시킨다.

계산 결과값을 별도의 변수에 저장해야하나 싶었는데, 그냥 재귀로 호출할 때마다 파라미터로 넘겨주는 방식으로 훨씬 편하게 성공할 수 있었다.

코드

class Solution {

    private static int count;

    public int solution(int[] numbers, int target) {

        dfs(numbers, 0, 0, target);
        return count;
    }

    private void dfs(int[] numbers, int index, int result, int target) {

        if (index == numbers.length) {
            if (result == target) count++;
            return;
        }

        dfs(numbers, index + 1, result + numbers[index], target);
        dfs(numbers, index + 1, result - numbers[index], target);
    }
}

---

풀이 (2021.05.29)

static 변수 없이 재귀로만 더 간단하게 풀었다.

코드

class Solution {
    
    public int solution(int[] numbers, int target) {
        return dfs(numbers, 0, 0, target);
    }
    
    private int dfs(int[] numbers, int index, int value, int target) {
        if (index == numbers.length) {
            if (value == target) return 1;
            else return 0;
        }
        
        return dfs(numbers, index+1, value+numbers[index], target) 
            + dfs(numbers, index+1, value-numbers[index], target);
    }
}