타겟 넘버 - level2 (python,java)

문제

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

프로그래머스

 

풀이

문제를 봤을때 먼저 떠오르는 방법은 모든 경우의 수를 다 확인하는 방법이다. 숫자 하나당 +와 -가 가능하므로 숫자가 n 개일때 나올수 있는 조합의 갯수는 2x2x2x2...x2 = 2^n 이다. 

문제에서 입력으로 숫자의 갯수는 최대 20이라고 했으므로 2^20 은 1억이 안되는 숫자로 1초도 걸리지 않는다.

따라서 모든 경우의 수를 다 확인하는 완전 탐색으로도 시간내에 풀이가 가능하다.

또한 완전 탐색이므로 bfs,dfs 를 이용해서 풀수 있다.

 

bfs 풀이

문제에 주어진 예제 2번을 그래프 형태로 그리면 다음과 같다. 

 

 

파이썬은 재귀 함수 호출 제한이 있으므로 BFS를 사용해서 풀고, 자바는 DFS를 사용해서 풀었다.

 

 

코드

python

from collections import deque

def solution(numbers, target):
    answer = 0
    n = len(numbers)-1
    q = deque()
    q.append((numbers[0],0))
    q.append((-numbers[0],0))

    while q:
        add,idx = q.popleft() 
        if idx<n:
            idx+=1
            q.append((add+numbers[idx],idx))
            q.append((add-numbers[idx],idx))
        else:
            if add == target:
                answer+=1


    return answer

 

 

java

class Solution {
    int count=0;
    public int solution(int[] numbers, int target) {
        int answer = 0;
        dfs(numbers,0,target,0); // 재귀호출을 통한 dfs 구현
        answer = count;
        return answer;
    }
    public void dfs(int[] numbers,int depth, int target, int result){
        if(depth==numbers.length){
            if(target==result){
                count+=1; // 전역 변수 사용
            }
            return; // numbers배열에 모든 값을 확인 했으면 더이상 재귀는 진행 X
        }
        
        dfs(numbers,depth+1,target,result+numbers[depth]);
        dfs(numbers,depth+1,target,result-numbers[depth]);
    }
}