[프로그래머스]Lv.2 타겟넘버(파이썬)

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

코딩테스트 연습 - 타겟 넘버

문제만 딱 놓고보면

사람이 풀기에는 아주 간단한 문제이지만

실제 컴퓨터로 풀기에는 다소 어려워보일 수 있습니다.

처음에는 저렇게

2차원으로 그래프를 뽑아낼까 생각했습니다.

문제의 예시로보면

[1,1,1,1,1]

[-1,-1,-1,-1,-1]

이렇게 구성된 그래프 nums를 만들고

각각 하나씩 찾아간다는 느낌으로요.

그런데, 이 방식은

numbers의 길이에 따라서

위 아래를 계산하는 양이 달라질 수 있더군요.

예를들면

저 문제의 경우에는

for i in range(5)를 해주고

 for j in range(2)이렇게 해줄까 했는데

1번쨰 2번쨰 3번쨰를 이렇게 할까 생각하니

코드가 도저히 잘 짜지지 않았습니다.

이 문제를 풀 때,

분류가 DFS/BFS라고 되어있어

저는 조금 당황했습니다.

아니...숫자 더하는 거랑

길찾는데 쓰는 알고리즘이랑

무슨 연관성이 있나.

그러다가 직접 손으로 숫자들을 나열하고더하는 케이스들을 살펴보니숫자들을 더하는 방식이길찾는 방식이랑 상당히 유사함을 알 수 있었습니다.그래서 DFS방식을 활용해서 문제를 풀었고코드는 아래와 같습니다.

 

def dfs(idx, numb, hap, target):
    global answer

    if idx == len(numb):
        if hap == target:
            answer += 1
            return
        else:
            return
    else:
        dfs(idx + 1, numb, hap + numb[idx], target)
        dfs(idx + 1, numb, hap - numb[idx], target)


def solution(numbers, target):
    global answer
    answer = 0
    h = 0
    dfs(0, numbers, h, target)
    return answer

 

 

이 문제에서 global로 answer를 다루는 것으로dfs를 잘 활용했습니다.검색해보니, 파이썬은 global로 전역변수를 쓸 수 있어저런 식으로 아주 유용하게 활용할 수 있었습니다.