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

각 숫자에 + 또는 - 를 붙여 만들 수 있는 모든 합 중에서, 타겟 넘버와 같은 경우의 수를 구하는 문제.

 

1. 문제 유형

DFS

 

2. 내가 놓친 포인트

처음 떠올린 접근 : 처음에는 visited 같은 방문 체크가 필요한 문제인가 생각했고, 숫자를 선택하는 방식처럼 접근하려 했다.

오답 원인: dfs를 구현할 때 현재 숫자 하나만 보는 게 아니라, 현재 인덱스와 현재까지의 누적합을 같이 넘겨야 한다는 점을 놓쳤다.

 

3. 핵심 로직 & 해결 방법

핵심 조건: 각 숫자는 한 번씩 순서대로 사용하고, 매 위치마다 + 또는 - 두 경우로 나뉜다.

풀이 아이디어:

1. dfs 함수에 index와 currentSum을 넘긴다.
2. 현재 위치의 숫자에 대해 +numbers[index], -numbers[index] 두 방향으로 재귀 호출한다.
3. index == numbers.length가 되면 모든 숫자를 다 사용한 것이므로, 그때 currentSum == target이면 count를 증가시킨다.
4. 최종적으로 count에 누적된 값을 반환한다.

4. 구현 코드

import java.util.*;

class Solution {
    static int target = 0;
    static int count = 0;

    public int solution(int[] numbers, int target) {
        Solution.target = target;
        dfs(numbers, 0, 0);
        return count;
    }

    public void dfs(int[] numbers, int index, int currentSum) {
        if (index == numbers.length) {
            if (currentSum == target) {
                count++;
                return;
            }
            return;
        }

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

시간 복잡도: O(2^N) / 공간 복잡도: O(N)

---

 

인사이트

• 정답 코드에서 static을 안쓰는 구조를 생각해보라는 피드백을 받았다. 복습할 때는 이 부분을 다시 생각해서 풀어보자.

 

 

문제 출처 - https://school.programmers.co.kr/learn/courses/30/lessons/43165