Today I Learned

SK C&C 최종 탈락.. 아직 공부가 모자란가보다. 다시 코테 빡세게 준비해야한다. 이번 주는 토익이 만기라 토익 공부도 병행해야한다. 코테는 일단 프로그래머스의 dfs, bfs 문제 위주로 계속 풀어보려 한다.

타겟 넘버

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

• 문제
  numbers 자연수 숫자 배열이 주어지면 주어진 숫자대로 +와 -로 계산하여 target 숫자에 맞는 경우의 수를 찾는 문제

• 구현 과정
  배열을 한 번 순회해야하고 한 원소마다 +와 - 두 가지 경우가 있다.
  전체 순회를 한 번 하면서 원소를 끝까지 들어가면서 계산할 수 있는 dfs로 풀면 되겠다고 생각했다.
  끝까지 파고 들어가서 덧셈의 총합이 target과 같으면 answer를 하나씩 올리는 방식으로 구현을 생각했다.
  필요한 변수는 일단 반환 해야될 answer, 총합 sum, 깊이 depth가 필요했다.
  dfs를 재귀로 구현해야 했기에 따로 위의 변수로 선언할 필요까진 없고 재귀 함수의 매개변수로 관리하게 했다.
  단, answer는 클래스 전역에서 사용해야 하므로 static으로 선언해뒀다.
  depth가 배열의 길이까지 갔을 때, sum이 target과 같으면 answer를 하나 늘리는 식으로구현하고, depth가 배열의 길이가 아니면 sum에서 +와 -하는 재귀함수를 넣고 depth를 1씩 늘린다.

• 최종 코드

import java.util.*;
class Solution {
	 // dfs와 solution 둘 다 써야하므로 전역 선언
    private static int answer = 0;
    
    private static void dfs(int[] numbers, int target, int sum, int depth){
    // 깊이가 배열을 끝까지 탐색했으면 총합이 타겟과 맞는지 확인
        if (depth == numbers.length){
            if (target == sum) answer++;
            // 아니라면 +와 -를 재귀적으로 2번 수행 
        } else{
            dfs(numbers, target, sum+numbers[depth], depth+1);
            dfs(numbers, target, sum-numbers[depth], depth+1);
        }
    }
    
    
    public int solution(int[] numbers, int target) {
        dfs(numbers, target, 0, 0);
        return answer;
    }
}