[프로그래머스] Lv.2 타겟 넘버 (Java)

문제

풀이 1

• 단순히 모든 경우의 수를 전부 계산해보는 풀이이다.
• 각 숫자에 1또는 -1을 붙이는 작업을 비트에 대입한다.

  만일 numbers의 원소가 4개라면 각 숫자에 1또는 -1를 붙이는 작업을 할 때
  ++++,+++-,++-+,...,----의 2의 4제곱개의 경우의 수가 생긴다.
  여기서 +를 -1, -를 1으로(혹은 반대로) 바꿔 0000,0001,0010,...,1111 의 비트로 치환할 수 있다.

• 즉 모든 경우의 수를 비트로 나타내서 0인 경우 -1를 곱하고 1인 경우 1을 곱해 sum을 구한 뒤, target과 같다면 answer에 카운트해주었다.

class Solution {
    public int solution(int[] numbers, int target) {
        int answer = 0;
        for(int i=0;i<Math.pow(2, numbers.length);i++) {
            int sum = 0;
            String binaryStr = Integer.toBinaryString(i);
            while(binaryStr.length()<numbers.length) {
                binaryStr = "0"+binaryStr;
            }

            for(int j=0;j<numbers.length;j++) {
                if(binaryStr.charAt(j)=='0') {
                    sum += numbers[j]*(-1);
                }else{
                    sum += numbers[j];
                }
            }
            if(sum==target) answer++;
        }
        return answer;
    }
}

풀이 2

풀고나서 이 문제가 dfs/bfs로 분류되어 있는 것을 확인하였다.
다음은 dfs를 활용한 풀이이다.

다음과 같이 모든 경우의 수를 알아낼 수 있다.

• numbers[n]번째 숫자에 대해서
  (n에 +1을 곱하는 경우, 그 합이 target이 되는 경우의 수) + (n에 -1를 곱하는 경우, 그 합이 target이 되는 경우의 수) 를 알아낸다는 것이다.
• dfs(int[] numbers,int n,int sum,int target)에서 int n은 지금 몇 번째 숫자인지를, int sum은 지금까지의 숫자 합을 나타낸다.

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;
            else return 0;
        }
        
        return dfs(numbers,n+1,sum+numbers[n],target) + dfs(numbers,n+1,sum-numbers[n],target);
    }
}