99클럽 코테 스터디 34일차 TIL - [프로그래머스] 타겟 넘버 (Java)

📌 오늘의 학습 키워드

[프로그래머스] 타겟 넘버 (Java)
https://school.programmers.co.kr/learn/courses/30/lessons/43165

📌 공부한 내용 본인의 언어로 정리하기

문제 탐색하기

입력 : 사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target
출력 : 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수

가능한 시간복잡도

O(n)

알고리즘 선택

dfs

📌 코드 설계하기

1. dfs 메서드를 호출하여 탐색을 시작한다. 초기 인덱스는 0이고, 초기 합계는 0으로 설정한다.
2. dfs 메서드는 현재까지 합계 sum이 목표 값 target과 일치하는지 확인한다.
3. 숫자의 끝에 도달했을 때(next == numbers.length), 합계가 목표 값과 일치하면 answer 값을 증가시킨다
4. 현재 숫자를 더하는 경우와 빼는 경우에 대해 각각 재귀적으로 dfs를 호출한다.

📌 오늘의 회고

어떤 문제가 있었고, 나는 어떤 시도를 했는지

어떻게 해결했는지

무엇을 새롭게 알았는지

내일 학습할 것은 무엇인지

구현

📌 정답 코드

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

    // 재귀함수 DFS를 할 예정이라, 정답을 클래스 단위에서 관리
    private int answer = 0;

    // 재귀함수 DFS
    public void dfs(
            // 내가 사용할 숫자들
            int[] numbers,
            // 내가 다음에 사용할 차례의 숫자
            // 이번 DFS 호출에서 더하거나 빼거나 할 숫자는 numbers[next]
            int next,
            // 목표 값
            int target,
            // 이번 재귀까지 합한 값
            int sum
    ) {
        // 마지막 숫자를 쓴 시점에 next는 배열의 크기와 동일해진다.
        if (next == numbers.length) {
            // target 과 일치하는지 확인
            if (sum == target) this.answer++;

        }
        else {
            // 더한 다음 다음 숫자 결정
            dfs(numbers, next + 1, target, sum + numbers[next]);
            // 뺀 다음 다음 숫자 결정
            dfs(numbers, next + 1, target, sum - numbers[next]);
        }
    }

 
}