[Programmers/Java] 프로그래머스 타겟 넘버 문제풀이

문제 분류가 떡하니 DFS/BFS로 되어 있다.

문제를 읽다보니 bit masking으로도 풀이가 가능해서 bit masking으로 풀이한 코드를 공유하려고 한다.

 

비트 마스킹을 이용한 풀이

class Solution {
    public int solution(int[] numbers, int target) {
        int answer = 0;
        
        // 0 ~ 2^(numbers.length-1)
        for (int i = 0; i < (1 << numbers.length); i++) {
        	int sum = 0;
        	// 0이면(원소 미포함) -, 0 이 아니면(원소 포함) +
        	for (int j = 0; j < numbers.length; j++) {
        		if((i & (1<<j)) != 0) {
        			sum += numbers[j];
        		} else {
        			sum -= numbers[j];
        		}
			}
        	// 타겟 넘버인 경우 answer++
        	if(sum==target) answer++;
		}
        return answer;
    }
}

 

줄맞춤 제대로 맞춰서 올렸는데 왜 저렇게 나오는지 모르겠다..

 

비트마스킹 사용했을 때의 테스트 결과다.

 

 

 

아래는 dfs를 이용한 풀이

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

    	dfs(numbers, target, numbers[0], 0);
    	dfs(numbers, target, -numbers[0], 0);
        
        return answer;
    }
    
    private static void dfs(int[] numbers, int target, int sum, int idx) {
    	if(idx == numbers.length-1) {
    		if(sum == target) answer++;
    		return;
    	}
    	
    	dfs(numbers, target, sum+numbers[idx+1], idx+1);
    	dfs(numbers, target, sum-numbers[idx+1], idx+1);
    }
}

 

 

dfs로 풀었을 때의 테스트 결과다.

 

 

 

이중포문(bit masking)를 이용한 테스트 결과와 재귀(dfs)를 이용한 테스트 결과를 비교해보면

시간적으로나 공간적으로나 재귀로 풀이한 코드가 효율적이다.

 

보통 이중포문이 더 빠르고 좋다고 생각했는데, 생각보다 차이가 많이나서 놀랐다.

아무래도 주어지는 숫자가 최대 20개여서 (2^20) * 20 만큼 for문이 돌아서 그런가보다..