프로그래머스 - 타겟 넘버 (레벨2, swift)

문제 출처

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

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

 

문제 설명

n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.

  -1+1+1+1+1 = 3

  +1-1+1+1+1 = 3

  +1+1-1+1+1 = 3

  +1+1+1-1+1 = 3

  +1+1+1+1-1 = 3

사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

 

제한 사항

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

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

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

 

입출력 예

numbers	target	return
[1, 1, 1, 1, 1]	3	5

 

 

✨문제풀이

배열의 숫자들이 +인 경우와 -인 경우를 자식 노드로 놓고 DFS 방식으로 풀면 된다.

 

[1, 1, 1] 을 트리 형태로 표현하면 위와 같다

 

 

트리의 각 레벨을 numbers 배열의 index로 보면 된다

DFS함수는 다음 index의 수를 더하거나 빼주며 재귀적으로 호출한다.

자식노드가 더이상 없는 경우(index가 numbers 배열의 count와 같은 경우) 지금까지 계산한 값과 target을 비교해 보고 같은지 판단하면 된다.

 

DFS함수

  index: numbers배열의 index이다. 재귀적으로 호출해주며 +1을 해준다

  sum: index에 해당하는 numbers배열의 수를 더하거나 빼준 값이다. 재귀적으로 호출하며 더하거나 빼준다.