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

✏️ 문제

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

✏️ 풀이

배열을 순차적으로 탐색하면서 더하거나/빼는 두 가지의 경우의 수가 있다.

즉, 트리 구조로 생각할 수 있다.

이 트리를 DFS로 완전 탐색한다.

DFS로 각 수를 더하거나 빼서 경우를 재귀적으로 탐색하고, 마지막 depth에 도착하면 target과 같은지 검사한다.

✏️ 코드

count = 0

def dfs(number, depth, target, numbers):
    global count
    if depth == len(numbers):
        if number == target:
            count += 1
        return
    dfs(number + numbers[depth], depth + 1, target, numbers)
    dfs(number - numbers[depth], depth + 1, target, numbers)

def solution(numbers, target):
    global count
    dfs(0, 0, target, numbers)
    return count

전역변수 count를 선언해서 target과 같은 수가 나올 시 증가시켜주는 방식으로 구현했다.

✏️ 다른 사람 풀이

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

DFS를 따로 구현하지 않고 재귀만을 이용한 풀이이다.

탈출 조건은 다음과 같다.

numbers가 빈 배열이고 target이 0이 되면 모든 수를 사용했을 때 target이 되는 경우이므로 1을 반환한다.

target이 0이 아니고 numbers가 빈 배열이면 모든 수를 사용했으나 target과 다른 경우이므로 0을 반환한다.

numbers[0]을 더하는 경우와 빼는 경우를 각각 재귀호출하고 리턴 값을 더한다. 이 때 확인한 값을 제외하고 슬라이싱한 배열을 전달한다.

재귀 개념 자체를 잘 쓴 풀이라고 생각했다.

 

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

곱집합(Cartesian product)를 이용한 풀이이다.

전달받은 numbers배열을 "(양수, 음수)"의 튜플 형태로 다시 저장한 뒤, 이를 unpacking하여 product함수에 전달한다.

product함수를 통해 수의 모든 조합(곱집합)이 산출되고 이를 sum한 결과가 s에 담기게 된다.

이 중 target과 같은 것의 개수를 세서 반환한다.