문제

Programmers - 타겟 넘버

숫자들이 담긴 배열이 주어지고, 숫자끼리 + 혹은 - 연산을 했을 때, 타겟 넘버가 나오는 경우의 총 횟수를 찾아야 한다!

접근

처음엔 문제를 봤을 때, 머릿속으로 모든 연산자 조합을 다 구해서 연산하면 되겠다라는 생각을 했는데, 코드를 짜려고 키보드에 손을 올린 순간 뭐부터 해야할지 생각이 안떠올랐다.
일단 DFS로 찾아야하는건 알았는데, 어떻게 코드를 짜야할지 감이 안와서 손으로 그림을 그려보니 구현 방향이 보였다.

이렇게 포화 이진트리라는게 눈에 보였고, 그러면 DFS를 +연산하는것과 -연산하는걸 분리해서 계산하면 되겠다라는 결론에 도달했다.

알고리즘

1. 숫자들이 담긴 배열과 타겟 넘버를 클래스 멤버로 선언
2. 루트 node를 기준으로 +연산을 하는 경우와 -연산을 하는 경우로 나눔
3. leaf node에 도달했다면 최종 합산 값을 타겟 넘버와 비교해 총 횟수를 1 증가시킴

최종 코드

class Solution {
    int[] numbers;
    int target;
    int answer;
    public int solution(int[] numbers, int target) {
        this.numbers = numbers;
        this.target = target;
        
        findTargetNumber(0, 0);
        
        return answer;
    }
    
    // DFS
    public void findTargetNumber(int depth, int sum) {
        if (depth == numbers.length) {
            if (sum == target) answer++;
            return;
        }
        
        // 해당 depth에서 값을 더하는 경우
        findTargetNumber(depth+1, sum+numbers[depth]);
        // 해당 depth에서 값을 빼는 경우
        findTargetNumber(depth+1, sum-numbers[depth]);
    }
}

깨달았던 점

처음으로 손으로 그림을 그려서 문제를 접근하고 생각한 접근법대로 코드를 짰을 때, 한번에 돌아가니까 신기했다. 문제를 보고 바로 키보드에 손이 올라가는게 아니라, 정답을 찾기 위한 알고리즘을 손으로 그려보고 전체 윤곽이 그려진 상태에서 코드를 쳐야한다는 것을 처음 깨달은 순간이었다.
쉬운 문제라 이렇게 손으로 그려서 풀었을지 모르지만, 앞으로 다른 문제들을 만났을 때도 그림으로 먼저 문제를 이해하고 풀어가는 방식으로 풀어봐야겠다.
추가로, 값이 변하지 않는 numbers와 target과 같은 변수는 클래스 변수로 빼서 재귀 함수의 인자를 줄이는 방식으로 코테 풀이 스타일을 일관화 해야겠다.