[PGM_43165] 타겟 넘버 (java)

문제링크

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

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

문제풀이

👨🏻‍💻 핵심 스킬 👨🏻‍💻
 브루트포스 - 재귀

2021.11.02 - [CordingTest/Algolithm] - 브루트포스(2) 재귀

배열과 타겟넘버 두개의 인풋이 들어온다. 이 때 배열의 값을 적당히 + 혹은 -로 넣어주어 더해서 타겟 넘버를 만족시키는 경우의수를 모두 구하는 문제이다. 배열의 개수가 최대 20개 까지 들어올 수 있으며 경우의 수는 $2^n$로 시간내로 들어올 수 있으므로 브루트포스를 사용하였다.

 

브루트포스를 재귀로 구현을 하였고, 이 때 부호는 boolean 배열을 만들어 +인지 -인지 확인하여주는 방법으로 구현을 하였다.

구현코드

package pgm_43165;

public class Solution {
    public int solution(int[] numbers, int target) {
        boolean[] signs = new boolean[numbers.length];
        int answer = recursive(numbers,signs,0,target);
        return answer;
    }

    public int recursive(int[] numbers,boolean[] signs, int check,int target) {
        if(check == numbers.length){
            int result = 0;
            for(int i = 0; i < numbers.length; i++){
                int sign = signs[i] ? 1 : -1;
                result += numbers[i] * sign;
            }
            if(result == target)
                return 1;
            else
                return 0;
        }
        signs[check] = false;
        int value1 = recursive(numbers,signs,check+1,target);
        signs[check] = true;
        int value2 = recursive(numbers,signs,check+1,target);
        return value1 + value2;
    }
}

 

시간복잡도

배열의 크기를 n이라고 하면, $O(2^n)$이 된다.

잘못된 지식이나 궁금한 내용이 있을 경우 편하게 댓글 남겨주시면 감사하겠습니다 :)