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

문제 링크: programmers.co.kr/learn/courses/30/lessons/43165

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

 

문제 설명

모든 경우의 수를 DFS(깊이 우선 탐색)으로 확인해서 타겟 넘버를 만드는 경우를 셌습니다. 

 

 

 

소스코드

answer = 0

def dfs(idx, numbers, total_sum, target):
    global answer
    n = len(numbers)
    # 마지막 원소까지 계산했다면 return
    if idx == n - 1:
        # 타겟 넘버를 만드는 경우
        if total_sum == target:
            answer += 1
        return
    # 다음 원소를 더할 경우
    dfs(idx + 1, numbers, total_sum + numbers[idx + 1], target)
    # 다음 원소를 뺄 경우
    dfs(idx + 1, numbers, total_sum - numbers[idx + 1], target)

def solution(numbers, target):
    global answer
    dfs(-1, numbers, 0, target)
    return answer

 

 

 

 

다른 사람의 풀이

✔ 재귀를 이용한 풀이

예를 들어 numbers = [1, 2, 3, 4, 5], target = 6 일 경우를 생각해봅시다. 

만약 [2, 3, 4, 5]로 5 또는 7을 만들 수 있다면, 1을 더하거나 빼서 타겟 넘버인 6을 만들 수 있습니다. 

이와 같은 아이디어로 재귀 함수를 이용한 풀이는 다음과 같습니다. 

def solution(numbers, target):
    # numbers로 target을 만들 수 있는 경우
    if not numbers and target == 0 :
        return 1
    # numbers로 target을 만들 수 없는 경우
    elif not numbers:
        return 0
    else:
        # 리스트의 앞 원소부터 순서대로
        # (해당 원소를 더했을 때의 정답 개수) + (해당 원소를 뺐을 때의 정답 개수)
        return solution(numbers[1:], target-numbers[0]) + solution(numbers[1:], target+numbers[0])

 

 

✔ product를 이용한 완전 탐색 풀이

from itertools import product

def solution(numbers, target):
    _list = [(x, -x) for x in numbers]
    s = list(map(sum, product(*_list)))
    return s.count(target)