난이도

Level 2

문제

문제 바로가기

문제 검토

가능한 경우의 수를 판별하는 것이기 때문에 백트랙킹, 완전탐색, DFS, BFS 다 가능해보인다.
여기서 백트랙킹, 완탐은 데이터 셋이 적기 때문에 가능해보인다.

풀이

아이디어

//백트랙킹, 완전탐색으로도 풀릴 것 같으나 조건이 추가되지 않고 +,-일때의 가중치가 같으므로 DFS,BFS로도 충분히 풀릴 것으로 보임
//target부터 시작해서 0이 도달할 때까지로 하겠음
//가지치기는 +,-로 한다.
//모든 경우의 수를 판별하는 문제이다.

JAVA - 백트랙킹

import java.util.*;
class Solution {    
    static int cnt=0;    
    public int solution(int[] numbers, int target) {                
        back(target,0,numbers);
        return cnt;
    }
    public void back(int result,int depth,int[] numbers){     
        //depth가 끝까지 도달했는데 값이 0이라면 cnt+1
        if (depth==numbers.length){
            if(result==0){
                cnt+=1;
            }
            return;
        }        
        for(int i=0; i<2; i++){
            if (i==0){
                result+=numbers[depth];
                back(result,depth+1,numbers);
                result-=numbers[depth];
            }else{
                result-=numbers[depth];
                back(result,depth+1,numbers);
                result+=numbers[depth];
            }                   
        }        
    }
}

가장 먼저 풀이했던 방법이다.
백트랙킹을 사용해서 문제를 풀이했다.

JAVA - BFS

import java.util.*;
class Solution {
    static Queue<int[]> q;    
    static int cnt=0;    
    public int solution(int[] numbers, int target) {                
        bfs(target,0,numbers);
        return cnt;
    }
    public void bfs(int result,int depth,int[] numbers){        
        q=new LinkedList<>();
        q.add(new int[]{result,depth});
        while(!q.isEmpty()){
            int[] tmp=q.poll();
            int re=0,de=0;  
            de=tmp[1]+1;
            if(tmp[1]>=numbers.length){
                if(tmp[0]==0 && tmp[1]==numbers.length){
                    cnt+=1;
                }
                continue;
            }                      
            for(int i=0;i<2;i++){
                if(i==0){
                    re=tmp[0]+numbers[tmp[1]];
                }else{
                    re=tmp[0]-numbers[tmp[1]];
                }
                q.add(new int[]{re,de});
            }
        }
    }
}

BFS로도 풀어봤다.

JAVA - DFS

import java.util.*;
class Solution {  
    static int cnt=0;    
    public int solution(int[] numbers, int target) {                
        dfs(target,0,numbers);
        return cnt;
    }
    public void dfs(int result,int depth,int[] numbers){     
        //depth가 끝까지 도달했는데 값이 0이라면 cnt+1
        if (depth==numbers.length){
            if(result==0){
                cnt+=1;
            }
            return;
        }        
        for(int i=0; i<2; i++){
            if (i==0){                
                dfs(result+numbers[depth],depth+1,numbers);                
            }else{
                
                dfs(result-numbers[depth],depth+1,numbers);                
            }                   
        }        
    }
}

DFS로 풀었다.
이 문제에서 백트랙킹이나 DFS나 같은 시간복잡도를 갖게 될 것이다.
왜냐하면 가중치가 같고 조건이 추가되지 않기 때문이다.
다만 백트랙킹에서는 result변수를 공유하고 있고 dfs에서는 아예 인자로 넣어주고 있다.

걸린 시간

21:42 (첫 정답 기준)

총평

자바가 좀 익숙해져서 쉽게 풀 수 있었다.
파이썬으로는 훨씬 간결한 코드가 나올 것 같다.