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

 

출처 : 프로그래머스 코딩테스트 연습, https://programmers.co.kr/learn/courses/30/lessons/43165

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

 

 

풀이

 

def plus_minus(current, array, index, target, count):
    plus_node = current + array[index]
    minus_node = current - array[index]
    
    if index == len(array) - 1:
        if plus_node == target:
            count += 1
        
        if minus_node == target:
            count += 1
        
        return count
    
    index += 1
    
    return plus_minus(plus_node, array, index, target, count) + plus_minus(minus_node, array, index, target, count)

def solution(numbers, target):
    answer = plus_minus(0, numbers, 0, target, 0)

    return answer

 

DFS를 사용하기 위해 재귀함수로 풀었다.

진짜 처음으로 스스로 재귀함수를 구현해서 정답을 맞춘거라 많이 부족하지만...

로직은 이렇다.

 

 

 

 

1. 재귀함수로 0부터 시작해서 array[index]의 값을 +하는 plus_node와 -하는 minus_node를 구한다.

   재귀 시 index 값을 증가시키며 더해지거나 빼지는 값을 설정해준다.

2. index가 증가하다가 끝에 도달하면 plus_node와 minus_node를 구한 후 구한 값을 target과 비교한다.

3. target과 같다면 count를 증가시키고 count를 return한다.

4. return 된 count값을 모두 더해 target을 만드는 방법의 수를 구한다.

 

 

개선 풀이 : count 매개변수 제외

 

def plus_minus(current, array, index, target):
    plus_node = current + array[index]
    minus_node = current - array[index]

    if index == len(array) - 1:
        count = 0
        if plus_node == target:
            count += 1

        if minus_node == target:
            count += 1

        return count

    index += 1

    return plus_minus(plus_node, array, index, target) + plus_minus(minus_node, array, index, target)

def solution(numbers, target):
    answer = plus_minus(0, numbers, 0, target)

    return answer

 

count는 굳이 매개변수로 줄 필요가 없다.

 

---

 

시간 복잡도

 

-(라고 적는 이유는 계산을 못해서 ㅎ)

 

 

다른 사람의 풀이를 보면서 알게 된 점

 

if not 리스트

 

test = []

if not test:
    print('Hello')
   
# Hello

 

리스트가 비었음을 확인하는 코드를 if not으로 구현할 수 있다.

 

 

고찰

 

재귀는 해설을 보면 이해는 가는데 직접 구현하려면 너무...... 막막하다.

 

재귀함수는 순환되지 않고 종료되는 base case가 있어야하고

모든 case가 base case로 수렴해야 재귀함수를 만들 수 있다.

 

내 코드에서는 base case가 행렬의 마지막 성분을 참고하거나 참고한 후로 생각하고 짰기 때문에

모든 case를 base case로 수렴시키기 위해서 index를 증가시키면서 만들어야한다는 것을 알 수 있다.

 

재귀로 꾸미려면 return에 함수를 넣는게 필요한데
매개변수 값과 return값을 어떤 값으로 줄지를 잘 생각해야 return에 함수를 넣어 처리할 수 있다.
이 문제 같은 경우는 binary tree를 구현해서 값을 계산하도록 문제를 짰는데,
binary tree로 구현하면 plus와 minus로 값이 나오는 2개라서 이걸 어떻게 return해서 처리할 지 고민이 많았다.
결국 count라는 단일 변수로 처리해서 return했다.