프로그래머스 LV2 - 타겟넘버

문제 링크

풀이 1 (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

풀이 해석

• queue를 통해 + - 값을 append하고 queue가 빌때까지 pop을 반복한다
• pop을 하며 index값을 증가시키며 다음값들을 더하고 빼주고 이를 append 한다
• 위 과정에서 temp == target일 경우 answer값을 증가시키며
• queue가 비었을 때 최종결과를 도출해낸다

풀이 2 (DFS)

def solution(numbers, target):
    n = len(numbers)
    answer = 0
    def dfs(idx, result):
        if idx == n:
            if result == target:
                nonlocal answer
                answer += 1
            return
        else:
            dfs(idx+1, result+numbers[idx])
            dfs(idx+1, result-numbers[idx])
    dfs(0,0)
    return answer

풀이 해석

• 재귀함수를 통해 idx를 1씩증가시켜 값을 계속 더해간다
• idx == n일 경우 result == target을 하여 이를 만족할 경우 answer 값을 증가시킨다
• solution 안에 dfs함수를 만들어 호출하였다
• nonlocal 을 이용해 answer를 정의하였다