타겟넘버

이것도 완전탐색으로 풀어야겠다는 감이왔다. 어제 풀었던걸 응용해봐야겠다 싶다가 -인경우도 생각해봐야해서 다르게 생각했다.

재귀로도 물론 풀수 있지만 비트마스킹을 사용해 풀수도있다.

기본적인 풀이 과정을 요약하면 이렇다. 주어진 num 는 모두 양수니, 모든 원소를 음수로 바꾼 min를 만들어서 깊이우선탐색을 진행한것이다.

 

ㅇ 비트마스크 (bit mask)

이진수를 이용해 연산을 하면 빠르게 연산이 가능하다. 이진수는 0 or 1만을 이용함.

비트마스크는 수행시간이 대부분O(1)로 다른 자료구조보다 더 빠르다. 

https://wogud6792.tistory.com/63

비트마스크 (BitMask) 알고리즘

ㅇ 코드

public static int solution(int[] numbers, int target) {
        int n = numbers.length;
        int[] min = new int[n];
        for (int i = 0; i < n; i++) {
            min[i] = -numbers[i]; // num 배열의 각 원소를 음수로 변환하여 min 배열에 저장
        }

        int count = 0;
        //이진표현에서 1은 해당원소가 선택되었음을 나타내고 0은 선택되지 않음을 나타냄
        for (int mask = 0; mask < (1 << n); mask++) { 
            int sum = 0;
            for (int i = 0; i < n; i++) {
            	// mask에서 i번째 비트가 설정(1) 되어있는지 확인. 설정되어있으면 num에서 선택한것이므로 
                if ((mask & (1 << i)) != 0) {
                    sum += numbers[i]; // num 배열에서 선택한 원소의 값을 더함
                } else {
                    sum += min[i]; // min 배열에서 선택한 원소의 값을 더함
                }
            }
            //합이 타겟과 일치하면 count++
            if (sum == target) {
                count++;
            }
        }
        return count;
    }

 

ㅇ 다른분들의 풀이

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

깊이우선 탐색을 사용해 푼걸 확인할수 있다.

깔끔하니 잘 푸셨다.