[프로그래머스] 타겟넘버 문제 풀이 (BFS)

문제 소개

오늘 풀었던 프로그래머스 타겟 넘버 문제를 정리합니다. 오랜만에 다시 알고리즘 풀이를 시작했습니다. 다시 매일 화이팅~!

주어진 숫자 배열에서 각 숫자에 + 또는 -를 붙여서 원하는 타겟 넘버를 만들 수 있는 경우의 수를 구하는 문제입니다.

문제 링크: 타겟 넘버 - 프로그래머스

---

문제 접근 방식

이 문제는 다음과 같은 방식으로 접근했습니다:

1. 이 문제는 모든 경우의 수를 탐색해야 하므로 완전 탐색(Brute Force) 방식이 적절합니다.
2. 각 숫자에 + 또는 -를 붙이는 모든 조합을 탐색해야 하므로, DFS(백트래킹) 또는 BFS를 활용할 수 있습니다.

---

해결 과정 및 코드

핵심 아이디어

1. 각 숫자에 대해 +와 -를 적용한 경우를 탐색
2. 탐색이 끝났을 때 목표 값(target)과 동일한 경우 answer 증가

코드

시간 복잡도 : N이 최대 20이므로 최대 탐색 횟수는 2^20 ≈ 1,000,000 → 브루트포스 탐색 가능

import java.util.*;

class Solution {
    static int answer = 0;
    public int solution(int[] numbers, int target) {
        bfs(numbers, 0, target, new boolean [numbers.length]);
        return answer;
    }
    
    public void bfs(int[] numbers, int idx, int target, boolean [] minus){
        if (idx >= numbers.length){
            int sum = 0;
            for (int i = 0; i < numbers.length; i++){
                if (minus[i]) sum -= numbers[i];
                else sum += numbers[i];
            }
            if (target == sum) answer++;
            return ;
        }
        minus[idx] = true;
        bfs (numbers, idx+1, target, minus);
        minus[idx] = false;
        bfs (numbers, idx+1, target, minus);
    }
}

 

또한 minus를 통해 +,- 기록하고 마지막에 검사할 수 있지만, 아래 다른 분들 풀이처럼 그냥 바로 계산할 수 있습니다.

class Solution {
    public int solution(int[] numbers, int target) {
        int answer = 0;
        answer = dfs(numbers, 0, 0, target);
        return answer;
    }
    int dfs(int[] numbers, int n, int sum, int target) {
        if(n == numbers.length) {
            if(sum == target) {
                return 1;
            }
            return 0;
        }
        return dfs(numbers, n + 1, sum + numbers[n], target) + dfs(numbers, n + 1, sum - numbers[n], target);
    }
}