Skip to main content

[Java] 43165 타겟 넘버

1. 문제

타겟 넘버

image.png

image.png

2. 접근 방법

  1. 각 숫자마다 연산자로 두 가지 선택지가 있다. → + 또는 -
  2. DFS로 모든 경우를 탐색하면서 합계를 누적한다.
  3. 모든 숫자를 다 사용한 시점은 (depth == numbers.length)에 합이 target과 같으면 count++;

3. 정답 코드

DFS

class Solution {
    int answer = 0;
    
    public int solution(int[] numbers, int target) {
        dfs(numbers, target, 0, 0);
        return answer;
    }
    
    private void dfs(int[] numbers, int target, int depth,  int sum) {
        // 모든 숫자를 다 사용했을 때
        if (depth == numbers.length) {
            if (sum == target) {
                answer++;
            }
            return;
        }
        
        //현재 숫자 더하는 경우
        dfs(numbers, target, depth + 1, sum + numbers[depth]);
        
        // 현재 숫자를 빼는 경우
        dfs(numbers, target, depth + 1, sum - numbers[depth]);
    }
}

return 

if (depth == numbers.length) {
    if (sum == target) {
        answer++;
    }
    return;
}

1. 모든 숫자를 다 사용했을 때 (depth == numbers.length)
→ 이제 더 이상 탐색할 숫자가 없으니까 여기서 탐색을 종료해야 한다.

2. 합이 target 과 같으면 answer++

3. 여기서 조건 검사가 끝났으면 더 내려갈 재귀 호출이 없으니까 return;으로 그냥 메서드를 끝내는 것이다. 만약에 return을 안 하면 dfs(..., sum + numbers[depth]) 같은 코드로 내려가려 하기 때문에, 불필요하게 실행되거나 ArrayIndexOutOfBounds 에러가 날 수 있다.)

  • return; = 현재 메서드 즉시 종료 (값은 반환하지 않음)
  • return 값; = 현재 메서드 즉시 종료 + 값을 반환

return 없으면?

private void dfs(int[] numbers, int target, int depth, int sum) {
    if (depth == numbers.length) {
        if (sum == target) {
            answer++;
        }
        // return 없음
    }

    dfs(numbers, target, depth + 1, sum + numbers[depth]); // 계속 실행됨
    dfs(numbers, target, depth + 1, sum - numbers[depth]);
}

BFS

import java.util.*;

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

        Queue<int[]> queue = new LinkedList<>();
        // {현재까지 합, depth}
        queue.add(new int[]{0, 0});

        while (!queue.isEmpty()) {
            // 큐가 빈 것이 아니라면
            int[] current = queue.poll();
            int sum = current[0];
            int depth = current[1];

            // 모든 숫자를 다 사용했으때
            if (depth == numbers.length) {
                if (sum == target) {
                    answer++;
                }
            } else {
                // 현재 숫자를 더하는 경우
                queue.add(new int[]{sum + numbers[depth], depth + 1});
                // 현재 숫자 빼는 경우
                queue.add(new int[]{sum - numbers[depth], depth + 1});
            }
        }
        
        return answer;
    }
}

queue에 담는 원소는 두 가지 정보이다.

  • sum = 지금까지 만든 합
  • depth = 몇 번째 숫자까지 썼는지

처음에는 아직 아무 숫자도 사용하지 않았고, 합계도 0이기 때문에 {0, 0} 으로 초기화한다. 

while (!queue.isEmpty()) {
    // 큐가 비어있지 않다면 하나 꺼내기
    int[] current = queue.poll();
    int sum = current[0];
    int depth = current[1];

모든 숫자를 다 사용했을 때(depth == numbers.length) 라면 더 이상 확장하지 못한다. 그 시점의 합이 target과 같으면 answer++로 경우의 수 1개를 추가해준다.

아직 탐색할 숫자가 남아 있다면

  • sum에+numbers[depth]한 새로운 합을 큐에 넣고
  • sum에 -numbers[depth]한 새로운 합을 큐에 넣는다.

그래서 큐에는 매 단계에서 앞 숫자를 “더한 경우”와 “뺀 경우” 두 가지 상태가 들어가게 되고, 결국 배열 안에 있는 모든 숫자를 다 쓸 때까지 앞전 합계에 그다음 숫자를 더한 경우와 뺀 경우로 가지치기처럼 계속 분기해서 모든 경우의 수를 탐색하는 것이 된다. 

// 현재 숫자를 더하는 경우
queue.add(new int[]{sum + numbers[depth], depth + 1});
// 현재 숫자를 빼는 경우
queue.add(new int[]{sum - numbers[depth], depth + 1});

이렇게 하면 모든 경우가 큐 안에서 너비 우선으로 탐색된다.


Back to top