[Programmers] target number.py (BFS, DFS)

#. Problem

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

* The copyright in this matter is in Programmers

n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 

예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.

사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때

 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

    - 주어지는 숫자의 개수는 2개 이상 20개 이하입니다.

    - 각 숫자는 1 이상 50 이하인 자연수입니다.

    - 타겟 넘버는 1 이상 1000 이하인 자연수입니다.

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

    - 주어진 수를 적절히 더하거나 빼서 타켓 넘버를 만들기

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

  1. 재귀함수를 사용

     numbers list에서 하나씩 숫자를 사용하여 양수일 경우와 음수일 경우를 각각 재귀함수에 넣어주고

    재귀함수에서는 계속해서 다음 요소들의 양수일 경우와 음수일 경우를 더해줌

    인덱스가 numbers의 크기에 도달했을 때, numbers의 요소들의 합이 target과 같은지 확인하고

    같으면 answer을 1 증가시켜준다.

    초기에  

    sum = (numbers[i])*(-1) + calculate(numbers, target, sum, i+1)

    sum = numbers[i] + calculate(numbers, target, sum, i+1)

    이런 방식을 떠올렸는데, 생각해보니 sum 변수가 2개가 되어버려서 return sum을 해도 중복 사용이 되어버려서 무용지물이라는 것을 깨달았다...

    결국 list의 각 요소들을 건드리고 마지막에 sum(list)를 하는 방법을 택했다.

    말은 쉬운데 재귀함수 구현이 너무 헷갈린다..ㅋ_ㅋ

    

#. Code

def solution(numbers, target):
    global cnt
    cnt = 0
 
    calculate(numbers, target, 0)
    return cnt
 
def calculate(numbers, target, i):
    if i == len(numbers):
        if sum(numbers) == target:
            global cnt
            cnt += 1
    else:
        numbers[i] *= 1
        calculate(numbers, target, i + 1)
 
        numbers[i] *= -1
        calculate(numbers, target, i+1)

  - (2~3) global을 사용하여 최종 result인 cnt 변수를 전역변수로 설정한다.

    (5) numbers, target, index를 재귀함수에 넣어서 작동!

    (9~12) index가 numbers의 크기와 같아졌을 때, 한 과정 (+1 +1 +1 +1 +1)이 완료된 것이므로

             numbers 요소들의 합이 target과 같다면 전역변수 count를 1 증가시켜준다.

    (14~18) 여기가 중요하다..!

               먼저 numbers의 0번째 요소부터 양수일 경우와 음수일 경우를 나누어 다시 재귀함수에 넣어준다.

               line 14는 i번째 요소가 양수일 경우이고,

               line 17은 i번째 요소가 음수인 경우이다.

               동작을 써보자면..  numbers = [1, 1, 1] 일 경우,

               i = 0,  [ 1,

               i = 1,  [ 1, 1

               i = 2,  [ 1, 1, 1] 

               i = 3, line 9로

               i = 2,  [ 1, 1, -1]  

               i = 3,  line 9로

               i = 1,  [ 1, -1

               i = 2,  [ 1, -1, 1]

               i = 3,  line 9로

               i = 2,  [ 1, -1, -1]

               i = 3,  line 9로

               i = 0,  [ -1,

               i = 1,  [ -1, 1

                ...       ...

               이러한 방식으로 동작한다.

               재귀함수는 매우 헷갈리므로 이렇게 동작을 써보면서 코드를 작성하면 그나마 덜 헷갈릴 수 있다.

#. Other code

from itertools import product
def solution(numbers, target):
    l = [(x, -x) for x in numbers]
    s = list(map(sum, product(*l)))
    return s.count(target)

 - (3)번 과정을 통해 [(1, -1), (1, -1), (1, -1), (1, -1), (1, -1)] 와 같이 사용 가능한 음-양수를 튜플로 저장한다.

       튜플로 저장하는 이유는 product함수를 보면 매개변수로 tuple이 들어간다.

   (4) list를 product함수로 곱집합 수행 후 sum을 해주면

       [5, 3, 3, 1, 3, 1, 1, -1, 3, 1, 1, -1, 1, -1, -1, -3, 3, 1, 1, -1, 1, -1, -1, -3, 1, -1, -1, -3, -1, -3, -3, -5]

      와 같은 결과를 얻을 수 있다. 

      참고> list(product(*l)) 의 결과로는 주어진 숫자(음-양수)로 조합 가능한 모든 경우의 수가 나온다

              [(1, 1, 1, 1, 1), (1, 1, 1, 1, -1), (1, 1, 1, -1, 1), (1, 1, 1, -1, -1), (1, 1, -1, 1, 1), ...

              여기서 *가 무슨 의미인지 모르겠다.. itertools documentation에도 없던데..

      여기서 target과 같은 요소의 개수를 return

    * 재귀함수보다는 덜 복잡하게 접근할 수 있는 코드인것 같다.