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

https://school.programmers.co.kr/learn/courses/30/lessons/43165

 

내 코드

def solution(numbers, target):
    answer = recursion(numbers, -1, 0, target)
    return answer

def recursion(numbers, idx, result, target):
    idx += 1
    
    if idx < len(numbers):
        cnt1 = recursion(numbers, idx, result + numbers[idx], target)
        cnt2 = recursion(numbers, idx, result - numbers[idx], target)
        return cnt1 + cnt2
        
    else:
        if result == target:
            return 1
        return 0

재귀 너무 오랜만이라 어떻게 break point 잡는지도어버버 헤매다가 어찌 저찌 해결은 했다 다만 이렇게 오래 생각할 문제였나 싶은 심란함을 안고..

 

타 풀이 참조 개선 코드

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

따로 회귀 함수를 만들지 않아도 soluiton 함수만으로 저렇게 numbers와 target을 잘라내는 걸 기준으로 break point 만들어서 대단했다. 시작 point도 나처럼 안헷갈리고..

 

시간 초과난 재도전

열받네.. 테스트 하나가 시간초과 났다

answer = []
def solution(numbers, target):
    if len(numbers) == 1:
        if target - numbers[0] == 0:
            answer.append(1)
        elif target + numbers[0] == 0:
            answer.append(1)
        else:
            return 0
    else:
        solution(numbers[1:], target - numbers[0])
        solution(numbers[1:], target + numbers[0])
        
    return sum(answer)

저렇게 answer 따로 두고 추가 추가 추가 한걸 합하는건 왜 시간이 소요가 많이 될까..

왜 나는 저 생각을 못했지..!?