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

---

접근 방법

문제의 패턴을 단순화시켜서 접근을 해보면, n개의 숫자들의 연산에서 (n-1)개까지의 숫자들 연산 후 n번째 숫자를 더할 것이냐, 뺄 것이냐의 2가지 방법으로 분기할 수 있다.

 

즉, 입력 값 number가 [1, 2, 3, 4] 일 때, [1, 2, 3]의 연산 이후 마지막 숫자인 4를 더한 값과 뺀 값의 2가지 결과를 얻을 수 있다는 것이다. 이를 구현하기 위해 재귀함수를 활용할 수 있다.

 

전체 코드의 큰 흐름은 아래와 같다. 

 

1. 재귀 함수의 입력값으로 array와 현재 index, 현재 sum을 받는다.

2. 함수 내에서 array와 다음 index의 숫자에 대하여 sum에 더하거나 빼는 것을 반복적으로 호출한다.

3. 만일 index의 값이 전체 array의 길이와 같으면, 즉 맨 마지막 원소까지 sum 계산을 완료하면 all_ways에 해당 sum을 추가한다.

3. 함수 정의 후, 0번째 index에 대해 초기 호출을 해준다.

4. 그러면 재귀적으로 다음 인덱스를 호출하며 자동적으로 모든 분기의 연산을 수행한다.

5. all_ways 중, 조건을 만족하는(target과 일치하는) 경우의 수를 카운트한다.

---

def solution(array, target):
    all_ways = []

    def get_all_ways(array, current_index, current_sum):
        if current_index == len(array):
            all_ways.append(current_sum)
            return
        get_all_ways(array, current_index + 1, current_sum + array[current_index])
        get_all_ways(array, current_index + 1, current_sum - array[current_index])

    get_all_ways(array, 0, 0)

    target_count = 0

    for way in all_ways:
        if target == way:
            target_count += 1

    return target_count

 

---

참고 자료

https://www.inflearn.com/course/38%EA%B5%B0%EB%8D%B0-%ED%95%A9%EA%B2%A9%EB%B9%84%EB%B2%95-%EC%BD%94%ED%85%8C-%ED%95%84%EC%88%98-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98/dashboard

38군데 합격 비법, 2024 코딩테스트 필수 알고리즘 강의 | 딩코딩코 - 인프런