[프로그래머스] 타겟 넘버 - Java

문제 설명

 

코딩테스트 연습 - 타겟 넘버

 

풀이 : Success

소스 코드

class Solution {
    
    int[] numbers;
    int target;
    int maxIndex;
    int result = 0;
    
    public int solution(int[] numbers, int target) {
        this.numbers = numbers;
        this.target = target;
        maxIndex = numbers.length;
        dfs(0, 0);
        
        return result;
    }
    
    public void dfs(int index, int sum) {
        if (index == maxIndex) return;
        if (index == maxIndex -1 && (sum + numbers[index]) == target) result++;
        if (index == maxIndex -1 && (sum - numbers[index]) == target) result++;

        dfs(index + 1, sum + numbers[index]);
        dfs(index + 1, sum - numbers[index]);
    }
}

 

풀이 회고

해당 문제는 DFS를 통해 해결 했습니다. solution 메서드에서 숫자가 담긴 배열 numbers와 타겟 넘버 target을 파라미터로 받으면 이를 해당 클래스의 멤버 변수로 선언해주었습니다. 이는 dfs 메서드를 통해 재귀 함수를 반복적으로 호출 시 이 값들을 지속적으로 참조하기 위함이었습니다.

 

문제를 푸는 매커니즘은 배열로 주어진 숫자들이 각각 음과 양으로 이루어질 수 있는 모든 경우의 수를 탐색하여 각각의 경우의 수에서 타겟 넘버와 일치하는지 확인하는 것이었습니다.

 

이를 위해 dfs 메서드에서는 두개의 dfs 메서드를 재귀 호출하게 되는데, 하나는 현재 index 값의 배열 값을 더해주면서 재귀하도록, 다른 하나는 현재 index 값의 배열 값을 빼주면서 재귀하도록 했습니다.

 

이때 현재 index 값의 배열 값을 계속 더해주는 루트(route)로 재귀한다면 주어진 모든 수를 더하는 경우의 수가 생길 것이고, 현재 index 값의 배열 값을 계속 빼주는 루트(route)로 재귀한다면 주어진 모든 수를 빼는 경우의 수가 생길 것입니다.

 

실제로는 현재 index 값의 배열 값을 더해주거나 빼주었다가 또 다시 다음 index 값의 배열 값을 더해주거나 빼주었다가 하면서 모든 경우의 수를 탐색하게 됩니다.

 

이 문제의 경우 백준-1182 "부분수열의 합" 문제를 풀이 방식과 상당히 유사하여 이 문제를 풀었었던 방식을 참고하여 풀이할 수 있었습니다. 백준-1182 "부분수열의 합"의 문제 풀이 방식은 다음 글을 통해 확인할 수 있습니다.

 

[백준 - 1182] 부분수열의 합 - Java

 

참고자료

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