[프로그래머스] 타겟넘버

문제

numbers를 더하고 빼서 target number를 만드는 횟수를 return

해결방향

자식 노드 생성후 dfs(깊이탐색)-> 재귀함수

• 깊이 우선 탐색의 경우 - 모든 친구 관계를 다 살펴봐야 할지도 모름
• 너비 우선 탐색의 경우 - Sam과 가까운 관계부터 탐색
  출처: https://devuna.tistory.com/32 [튜나 개발일기:티스토리]

python

1. 단순하게 이중for문을 사용하여 모든경우의 수를 새로운 리스트에 추가한후 타겟값과같은 경우를 count
   실패: 2의 n승 다 돌아봐야 되서 시간초과 ->재귀함수 풀이 시도

def solution(numbers, target):
    answer = 0
    new = []
    num = numbers.pop(0)
    new.append(num)
    new.append(-num)
    
    for i in range(len(numbers)):
        num = numbers.pop(0)
        for i in range(len(new)):
            new_num = new.pop(0)
            new.append(new_num +num)
            new.append(new_num -num)
                
    return new.count(target)

2. 자식노드를 만드는 재귀함수 생각
   자식노드를만드는 과정: 재귀함수

def solution(numbers, target):
    answer = 0
    length = len(numbers)
    
    def loop(idx=0):
        if idx< length:
            numbers[idx]*=1
            loop(idx+1) #자식노드 만들기
            
            numbers[idx]*=-1
            loop(idx+1) #자식노드 만들기
            
        elif sum(numbers) == target:
            nonlocal answer
            answer+=1
            
    loop()
                
    return answer

JAVA

class Solution {
    static int answer = 0;
    
    public int solution(int[] numbers, int target) { 
        loop(numbers,target,0,0);
         return answer;
    }
    
    static void loop(int[] numbers, int target, int idx, int sum){
        if (idx<numbers.length){
            
            loop(numbers,target,idx +1,sum+numbers[idx]);

            loop(numbers,target,idx +1,sum-numbers[idx]);
        } 
        else if (sum == target){
            answer ++;
        }
    }
}

JAVA 주의점

global이나 nonlocal과 같은 전역변수 설정이 없어서 함수마다 매개변수를 매번 지정해줘야 한다 but 이를 이용해서 재귀 함수를 매우 간단히 표현할 수 있다.

JAVA 함수선언

public static int solution(numbers,target){}
/*return 값 필요*/
public static void solution(numbers,target){}
/*void: return값 필요 없음*/