Level 2 타겟 넘버 Python 3

https://programmers.co.kr/learn/courses/30/lessons/43165?language=python3 

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

 

최종 코드

• GitHub https://github.com/hwayeon351/Programmers-Algorithms/blob/main/level2_타겟넘버.py

hwayeon351/Programmers-Algorithms

answer = 0
def dfs(i, n_sum, numbers, target):
    global answer
    if i == len(numbers):
        if n_sum == target:
            answer += 1
        return
    dfs(i+1, n_sum+numbers[i], numbers, target)
    dfs(i+1, n_sum-numbers[i], numbers, target)

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

---

풀이 과정

풀이 시간 10분

모든 numbers의 항목을 더하거나 빼서 타겟 넘버를 만들 수 있는 방법의 수를 구하는 문제이다.

numbers를 idx 순서대로 탐색해서 더하거나 빼는 경우로 나누어 dfs를 재귀 호출 해주는 방식으로 문제를 해결하였다.

재귀 함수의 종료 조건은 모든 numbers 항목을 사용했을 때, 즉 idx 값이 len(numbers)인 경우이며, 이때 그동안 항목을 더하거나 뺀 결과(n_sum)와 target을 비교하여 같은 경우 카운팅 해주었다.

answer = 0
def dfs(i, n_sum, numbers, target):
    global answer
    
    #재귀 함수 종료 시점
    if i == len(numbers):
        if n_sum == target:
            answer += 1
        return
    
    #더하거나 뺀 경우로 나누어 재귀 함수 호출
    dfs(i+1, n_sum+numbers[i], numbers, target)
    dfs(i+1, n_sum-numbers[i], numbers, target)

def solution(numbers, target):
    dfs(0, 0, numbers, target)
    return answer
    
#시간복잡도 = O(2^n), 공간복잡도 = O(n)

재귀 함수는 더하거나 빼는 2가지로 각 항목을 탐색할 때마다 호출이 되기 때문에 시간복잡도는 = O(2^n)이다.

문제의 입력 조건이 numbers의 최대 길이가 20으로 주어졌으니, 최악의 경우 2^20의 시간이 소요된다.

보통 1초 당 반복문 수행 횟수가 1억(10^8)을 넘어가면 시간 제한을 초과할 가능성이 있다는 점에서 2^20은 10^6정도이므로 제한시간을 초과하지 않는다.