프로그래머스 lv2 타겟넘버

문제 링크

타겟넘버

풀이

class Solution {
    int answer = 0;
    
    public int solution(int[] numbers, int target) {
        dfs(numbers, target, 0, 0);
        return answer;
    }
    
    /**
     * 깊이 우선 탐색
     * @param numbers : 주어지는 배열
     * @param target : 원하는 사칙연산 결과의 값
     * @param sum : 현재까지의 사칙연산의 결과 ( 더하기가 되었던 빼기가 되었건 간에..)
     * @param depth : 현재 탐색중인 깊이
     */
    public void dfs (int [] numbers, int target, int sum, int depth){
    	// 만약에 깊이가 numbers배열의 길이와 같다면, 해당 탐색이 끝에 도달했다는 소리이기에 결과를 비교하면 된다.
        if(depth == numbers.length){
            if(target == sum){
            	answer++;
            }
        } else {
        	// 결과값에 더하기를 해주는 것과 빼기를 해주는 모든 경우를 체크해본다.
            dfs(numbers, target, sum + numbers[depth], depth + 1);
            dfs(numbers, target, sum - numbers[depth], depth + 1);
        }
    }
}

소감

• 이미 한 번 풀었던 문제다. 문제 풀이하는 곳에 풀이가 적혀있어서 뭔가 했는데, 예전에 풀었던 문제이었다.
• 안 푼 문제로 필터링걸었는데...뭔가 작동이 잘못되었나보다.
• 그나저나 나는 dfs/bfs 문제만 나오면 머리에 과부하가 걸린다. 멍청하다.
• 공포증이라도 있는건지 대가리가 안굴러간다. 대강 이진트리 그려보면서 어떻게든 규칙성을 잡아내려고 해도 안나온다.
• 결국은 또 풀었던 사람의 설명을 한 번 읽어보고 풀었다. 멍청하다.
• 관련 문제들을 자주 풀어서 익숙해지게 만들어야겠다.