[코딩테스트] Java 타겟넘버

제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
Programmers 알고리즘 고득점 Kit입니다.

포인트

DFS를 활용하여 재귀함수를 통해 타겟 넘버를 찾는 코드입니다. 익숙하면 금방 풀리겠지만, 저는 재귀와 같은 부분이 많이 헷갈려 조금 헤맸던 문제였습니다. 재귀함수를 통해 문제를 풀 때에는 종료 조건을 제일 중요하게 생각해야합니다.

소스코드

class Solution {
    int[] arr;
    int targetNumber, answer = 0;
    
    public void findTargetNum(int num, int cnt) {
        if (num == targetNumber && cnt == arr.length) {
            answer++;
            return;
        }
        if (cnt >= arr.length) return;
        
        findTargetNum(num - arr[cnt], cnt + 1);
        findTargetNum(num + arr[cnt], cnt + 1);
    }
    
    public int solution(int[] numbers, int target) {
        int n = numbers.length;
        arr = new int[n];
        targetNumber = target;
        
        for(int i = 0; i < n; i++) {
            arr[i] = numbers[i];
        }
        
        findTargetNum(-1 * arr[0], 1);
        findTargetNum(arr[0], 1);
        
        return answer;
    }
}

코드 설명

public void findTargetNum(int num, int cnt) {
    if (num == targetNumber && cnt == arr.length) {
        answer++;
        return;
    }
    if (cnt >= arr.length) return;

    findTargetNum(num - arr[cnt], cnt + 1);
    findTargetNum(num + arr[cnt], cnt + 1);
}

• num은 현재까지 계산된 합계이며, cnt는 현재 탐색중인 배열의 인덱스 입니다.
• 종료조건
  • num == targetNumber && cnt == arr.length:
    현재까지 계산된 값이 targetNumber와 같고, 배열의 모든 원소를 사용했다면 경우의 수를 1 증가시킵니다.
  • cnt >= arr.length
    배열의 끝까지 도달했지만 targetNumber에 도달하지 못하면 탐색을 종료합니다.
• 재귀 호출
  • findTargetNum(num - arr[cnt], cnt + 1):
    현재 숫자를 빼는 경우를 탐색합니다.
  • findTargetNum(num + arr[cnt], cnt + 1):
    현재 숫자를 더하는 경우를 탐색합니다.

public int solution(int[] numbers, int target) {
    int n = numbers.length;
    arr = new int[n];
    targetNumber = target;

    for(int i = 0; i < n; i++) {
        arr[i] = numbers[i];
    }

    findTargetNum(-1 * arr[0], 1);
    findTargetNum(arr[0], 1);

    return answer;
}

• 배열을 복사하고 타겟 넘버를 복사합니다. 전역변수로 사용해서 findTargetNum에서 사용하기 위함입니다.
• findTargetNum(-1 * arr[0], 1)
  첫 번째 숫자를 빼는 경우부터 시작합니다.
• findTargetNum(arr[0], 1)
  첫 번째 숫자를 더하는 경우부터 시작합니다.