[Python] 프로그래머스 lv.2 타겟 넘버 (+ nonlocal)

알고리즘 고득점 kit - 깊이/너비 우선 탐색 (DFS/BFS) - lv 2

 

문제분석

• n개의 음이 아닌 정수들
• 정수들의 순서를 바꾸지 않고, 적절히 더하거나 빼서 타겟 넘버를 만들려고 한다.

 

• numbers 배열 : 사용할 수 있는 숫자가 담긴 배열
• target : 타겟 넘버
• 배열 안의 숫자를 적절히 더하거나 빼서 타겟 넘버를 만드는 방법의 수 return

 

코드 설계

• dfs
• 배열 시작부터 넣고
• 갈 수 있는 다음 위치는 + or -
• 배열의 숫자를 모두 사용해야함
• 배열 안에 값이 모두 없으면 return

 

정답 코드

실패..

import sys
input = sys.stdin.readline()

num = [1, 1, 1, 1, 1]
operation = ['+', '-']
tar = 3

def solution(numbers, target):
    answer = 0

    return answer

def dfs() :
    oper = []
    if len(oper) == len(num):
        return oper
    for _ in range(len(num)) :
        oper.append()
        dfs()
        oper.pop()


print(solution(num, tar))

 

다른 사람 풀이 1 - dfs (깊이 우선 탐색)

https://velog.io/@ju_h2/Python-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-level2-%ED%83%80%EA%B2%9F%EB%84%98%EB%B2%84-BFSDFS

def solution(numbers, target):
    n = len(numbers)
    answer = 0
    
    def dfs(idx, result) : 
    	# idx : 현재 처리중인 배열의 index
        # result : 현재까지의 계산 결과
        
        if idx == n : # 모든 배열을 확인했다면 재귀 탈출
            if result == target : # target 넘버와 같다면
                nonlocal answer 
                answer += 1 # 타겟 넘버와 일치하는 경우 마지막으로 count
            return
        else : # 아직 모든 배열을 탐색하지 못했다면 
            dfs(idx+1, result+numbers[idx]) 
            dfs(idx+1, result-numbers[idx])
    
    dfs(0,0)
    return answer

• nonlocal : 상위 함수에 변수를 참조한다고 미리 선언
• ex) a 값을 상위 함수의 a 값을 사용한다. 

def test():
   a = 3

   def sum():
       nonlocal a
       a = 7
       return True

   sum()
   return a

result = test()
print(result)

# 7

• global vs nonloacl
  • global : 일반 함수 내에서 전역 변수를 사용할 때 사용
  • nonlocal : 중첩 함수 내에서 상위 함수의 변수를 사용할 때 사용

 

다른 사람 풀이 2 - deque를 이용한 bfs

from collections import deque

def solution(numbers, target):
    answer = 0
    queue = deque()
    n = len(numbers)
    queue.append([numbers[0],0])
    queue.append([-1*numbers[0],0])
    
    while queue:
        temp, idx = queue.popleft()
        idx += 1
        if idx < n:
            queue.append([temp+numbers[idx], idx])
            queue.append([temp-numbers[idx], idx])
        else:
            if temp == target:
                answer += 1
    return answer

 

다른 사람 풀이 3

def solution(numbers, target):
    if not numbers and target == 0 :
        return 1
    elif not numbers:
        return 0
    else:
        return solution(numbers[1:], target-numbers[0]) + solution(numbers[1:], target+numbers[0])

 

다른 사람 풀이 4

from itertools import product
def solution(numbers, target):
    l = [(x, -x) for x in numbers]
    s = list(map(sum, product(*l)))
    return s.count(target)