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

문제

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

[프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

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

풀이

문제 유형에도 써있듯이, DFS/BFS를 활용하여 풀 수 있는 문제이다.

문제에 대한 접근 방식을 생각해보면 +/-의 이진 트리 구조를 활용해서 연산 결과를 나타낼 수 있다.

그리고 스택이나 큐를 활용해 뽑아낸 수(현재 단계에서의 숫자)의 다음에 나올 숫자에 대한 +/-연산을 추가해주는 방식으로 풀이가 가능하다.

BFS 예) 1,1,1,1,1 -> [0] -> 0 : [1,-1] -> 1 : [-1,2,0] -> -1 : [2,0,0,-2] -> ...

DFS 예) 1,1,1,1,1 -> [0] -> 0 : [1,-1] -> -1 : [1,0,-2] -> -2 : [1,0,-1,-3] -> ...

def solution(numbers, target):
    answer = 0
    # dfs
    stack = [(0,-1)]
    while stack:
        tmp, idx = stack.pop()
        idx+=1
        if idx<len(numbers):
            stack.append((tmp+numbers[idx],idx))
            stack.append((tmp-numbers[idx],idx))
        else:
            if tmp==target:
                answer+=1

    return answer

def solution(numbers, target):
    # bfs
    answer = 0
    from collections import deque
    q = deque([(0,-1)])
    while q:
        tmp, idx = q.popleft()
        idx+=1
        if idx<len(numbers):
            q.append((tmp+numbers[idx],idx))
            q.append((tmp-numbers[idx],idx))
        else:
            if tmp==target:
                answer+=1

    return answer

다른 풀이

다른 풀이를 보던 중, 재귀함수를 활용해 신박한 방법으로 해결한 풀이가 있었다.

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])

 

PS : DFS/BFS에 대한 정석적인 문제에 대해서는 익숙해졌다고 생각했는데, 이러한 응용 문제는 더 연습할 필요가 있는 것 같다.