[programmers] 43165. target number

문제

43165. 프로그래머스 타겟넘버

분석

1. 이 문제는 numbers로 들어오는 모든 숫자에 대해서 +, -를 하여 가능한 모든 경우의 수를 탐색하여야한다. 따라서 완전탐색을 해야한다.
   이를 위해 BFS/DFS로 문제를 풀어보았다.

1. DFS

1-1. Base Case

• DFS를 구현할 때, 재귀함수에서 무한 루프를 돌지 않기 위해서는 base case를 잘 정의해주어야함.
• 이 경우는, numbers의 모든 number들에 대해 재귀를 돌았을 때이다. 즉, 코드로 구현하면 다음과 같다.

n = len(numbers)
dfs(depth, ...):
	# base case
    if depth == (n-1):
    	return

1-2. +, - 두가지 경우에 대한 생각

• 처음 시작할 때에도 첫 숫자에 대해 +,-일지를 잘 정의해주어야한다. 즉, 코드로 구현하면 다음과 같다.

	def dfs(depth, case, total):
    .
    .
    .
    
    ########### HERE ###########
    # plus
    dfs(0, 0, 0)
    # minus
    dfs(0, 1, 0)
    ############################

이를 유념해서 코드를 짜보자!

1-3. DFS 구현 코드

def solution(numbers, target):
    global count

    count = 0
    n = len(numbers)
    
    def dfs(depth, case, total):
        global count
        cur_v = numbers[depth]
        if case == 0:
            total = total+cur_v
        elif case == 1:
            total = total-cur_v
            
        if depth == (n-1):
            if total == target:
                count+=1
            return
        
        #next_v = numbers[depth+1]
        dfs(depth+1, 0, total)
        dfs(depth+1, 1, total)
            
    
    # plus
    dfs(0, 0, 0)
    # minus
    dfs(0, 1, 0)
    
    return count

2. BFS

# bfs
from collections import deque
def solution(numbers, target):
    global count
    n = len(numbers)
    cur_dep = 0
    count = 0
    queue = deque()
    queue.append((0, numbers[0]))
    queue.append((0, -numbers[0]))

    while queue:
        cur_dep, cur_tot = queue.popleft()
        if cur_dep == n-1:
            if cur_tot == target:
                count+=1
                
        # 다음 step: numbers의 idx 빠져나가면 안됌
        if cur_dep+1<n:
            # plus
            queue.append((cur_dep+1, cur_tot + numbers[cur_dep+1]))
            # minus
            queue.append((cur_dep+1, cur_tot - numbers[cur_dep+1]))
        
    return count

문제 출력 확인

if __name__ == "__main__":
    numbers = [1, 1, 1, 1, 1]
    target = 3
    
    answer = solution(numbers, target)
    print("answer: ", answer)

answer: 5