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

문제 설명

n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.제한사항

• 주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
• 각 숫자는 1 이상 50 이하인 자연수입니다.
• 타겟 넘버는 1 이상 1000 이하인 자연수입니다.

입출력 예

예제

입출력 예 설명

문제에 나온 예와 같습니다.

---

나의 풀이

나는 이 문제를 DFS를 사용해 풀었다.

2021.06.26 - 깊이 우선 탐색(DFS, Depth First Search) 파이썬 구현

깊이 우선 탐색(DFS, Depth First Search) 파이썬 구현

 

DFS는 스택을 사용하는데 일반적으로 직접적으로 사용하는 것보다 재귀를 사용하는 편이다.

왜냐하면 재귀는 시스템에서 사용하는 일종의 스택 구조이기 때문이다.

재귀를 사용할 때는 종료 조건을 잘 설정해주어야 한다.

이 문제에서는 numbers의 모든 숫자를 사용했으면 종료해주면 된다.

count = 0

def dfs(numbers, idx, target, num, total):
    global count
    total += num
    if idx == len(numbers)-1:
        if total == target:
            count += 1
        return
    dfs(numbers, idx+1, target, numbers[idx+1], total)
    dfs(numbers, idx+1, target, -numbers[idx+1], total)
    
def solution(numbers, target):
    numbers = [0]+numbers
    dfs(numbers, 0, target, numbers[0], 0)
    return count

우선 정답으로 사용할 count를 전역 변수로 선언했다. (실제 프로그래밍 환경에서 아주 안 좋은 방법이지만 코딩테스트는 정확하고 빠른 풀이가 좀 더 중요하므로 전역 변수를 사용했다. 밑에서 전역 변수를 사용하지 않는 코드도 소개할 것)

dfs() 함수는 numbers와 idx(인덱스)를 받는데 이것은 다음에 재귀적으로 호출할 dfs()에 넣을 수를 찾기 위함이다.

DFS와 재귀 함수에 대해 경험이 있거나 이론적으로 이해하고 있다면 어려운 코드는 아니다.

---

전역 변수 사용하지 않은 풀이

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

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

전역 변수를 사용했던 풀이에서는 numbers 맨 앞에 0을 붙여주었다. 하지만 위 풀이에서는 dfs()의 매개 변수로 idx+1과 num+numbers[idx]를 넘기는데 이렇게 되면 numbers[0]을 두 번 처리할 수 있으므로 numbers 맨 앞에 0을 별도로 붙여줄 필요가 없게 되는 것이다.

또한 total 매개변수도 num에 통합을 했다. num이 더해질 수에서 더해진 수로 의미가 바뀌었다.

numbers의 모든 숫자를 계산했을 때 target과 num이 같다면 1을, 다르다면 0을 반환하여 answer에 더해준다.

그러면 target과 같은 결과의 개수가 answer에 쌓이게 된다. 이 answer을 return해주면 정답이 된다.

 

테스트 결과