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

BFS, DFS 문제

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

프로그래머스

 

접근방식

• 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수 구하기 -> DFS로 풀어 모든 경우의 수 탐색
  
  • 특정 숫자를 변환하였을 때의 타겟 넘버를 만족하는지를 비교하여 가짓수(경우의 수) 구하는 것이므로 return값 설정

 

풀이코드  (실패, 오답-cnt를 전역변수로 선언)

import sys
sys.setrecursionlimit(10 ** 9)

cnt = 0
oper = [1, -1]

def dfs(valSum, idx, target, numbers):
    global oper, cnt

    if idx == len(numbers):
        if valSum == target:
            return 1
        else:
            return 0
    
    for j in range(2):
        num = numbers[idx] * oper[j]
        if idx + 1 <= len(numbers):
            cnt += dfs(valSum + num, idx + 1, target, numbers)
    return cnt
        
def solution(numbers, target):
    answer = dfs(0, 0, target, numbers)
    return answer

 

문제점

cnt 변수가 전역 변수로 선언되어 있다.
따라서, 모든 dfs 호출이 동일한 cnt 변수를 공유한다. 이는 재귀 호출이 일어날 때마다 cnt 값이 누적되어 의도하지 않은 결과를 초래한다.

 

💡 풀이코드 (성공)

import sys
sys.setrecursionlimit(10 ** 9)

oper = [1, -1]

def dfs(valSum, idx, target, numbers):
    global oper
    cnt = 0
    if idx == len(numbers):
        if valSum == target:
            return 1
        else:
            return 0
    
    for j in range(2):
        num = numbers[idx] * oper[j]
        if idx + 1 <= len(numbers): # list out of index 방지
            cnt += dfs(valSum + num, idx + 1, target, numbers)
    return cnt
        
def solution(numbers, target):
    answer = dfs(0, 0, target, numbers)
    return answer

 

 

👩🏻‍💻 위의 코드

• cnt를 전역변수 -> 로컬변수로 변경해주었다.
• idx가 numbers의 마지막 인덱스인 len(numbers) - 1보다 같거나 작다면 dfs를 재귀호출한다.
  • 즉, numbers의 마지막 인덱스의 변환값(num)까지 포함해서 valSum에 더하기 위해 다음과 같이 조건문을 작성해주었다.

if idx + 1 <= len(numbers):

 

• 만약 위의 조건문에서 마지막으로 만족된 경우라면, valSum과 target을 비교하여 값이 같다면 1을, 다르다면 0을 리턴한다.

cnt = 0
if idx == len(numbers):
    if valSum == target:
        return 1
    else:
        return 0