[프로그래머스][DFS/BFS] python - 타겟넘버

문제 설명

n개의 음이 아닌 정수들이 있습니다.

이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다.

예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.

-1+1+1+1+1 = 3

+1-1+1+1+1 = 3

+1+1-1+1+1 = 3

+1+1+1-1+1 = 3

+1+1+1+1-1 = 3

사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

 

첫 번째 풀이

DFS를 이용한 풀이

answer = 0
def graph(signs, numbers, target):
    global answer
    if len(signs) == len(numbers):
        if check(signs, numbers, target) :
            answer += 1
        return

    for i in range(2):
        graph(signs + [i], numbers, target)

def check(signs, numbers, target):
    summation = 0
    for s, n in zip(signs, numbers):
        if s :
            summation += n
        else :
            summation -= n
    return True if summation == target else False

def solution(numbers, target):
    signs = []
    graph(signs, numbers, target)

    global answer
    return answer

어떻게 효율적으로 부호를 탐색할 수 있을까 생각해보았는데 어쩔수없이 모든 경우의 수를 체크해주어야하는 문제였다.

 

부호를 저장하는 배열을 만들어서 따로 관리해주었다.

빈 배열에서 시작해 위의 그림처럼 recursion이 더해질수록 부호를 하나씩 더해주는 방식으로 graph 함수를 구성했고,

recursion이 계속되어 numbers의 길이와 같아졌을때,

부호에 따라 numbers의 숫자를 더하거나 빼주어 결과를 구하는 방식으로 구현했다.

 

! 부스트캠프 챌린지를 하면서 알고리즘 공부를 따로 하진 않았지만 흔히 말하는 ~컴띵~이 늘었다고 생각되었다. 예전같았으면 풀지 못했을 것 같은 문제인데 어렵지 않게 풀 수 있었어서 매우 뿌듯하다 !

재귀 함수 작성할때 return문 작성안해서 잠깐 어리둥절하긴 했지만...

 

풀고 나서 다른 사람의 풀이를 참고 해서 개선해보았다.

 

개선하기

answer = 0
def graph(numbers, target, depth):
    global answer
    if depth == len(numbers):
        if sum(numbers) == target :
            answer += 1
        return

    graph(numbers, target, depth + 1)
    numbers[depth] *= -1
    graph(numbers, target, depth + 1)

def solution(numbers, target):
    graph(numbers, target, 0)
    global answer
    return answer

 

프로그래머스 - 타겟 넘버 (DFS, BFS) Python

부호를 저장하는 배열을 따로 만들지 않고 직접 numbers 배열에 -1을 곱하는 방식으로 조작해서 문제를 해결하는 방식이다.

check라는 함수를 따로 만들지도 않고 별도의 배열을 만들지 않아도 되어서 훨씬 간결하게 코드를 작성할 수 있다.

참고한 블로그에서는 global 도 사용하지 않는 방식으로 구현했지만,

파이썬이 아니라 자바로 풀었다면 Main 함수의 멤버변수로 선언해서 해결할 수도 있기때문에 그냥 global을 사용해서 문제를 해결했다.