Lv2. 타겟 넘버

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

1. 풀이 설명

1. 아래와 같은 tree 를 생각하면서 문제를 풀었다.

																					n
                        0											level 1			
                        
          1                             -1							level 2			1
          				
    2           0               0               -2					level 3			1
    
3       1   1       -1      1       -1      -1      -3				level 4			1

2. parent 리스트에 0을 넣어 초기화하며, numbers for문을 돌면서 (n) 트리가 한 층씩 내려간다.

3. parent 아이템에 +n, -n 을 한 값들로 parent 를 업데이트 해준다.

4. parent 리스트 아이템들 중에서 target 의 개수를 반환한다.

2. 나의 풀이

python

def solution(numbers, target):
    parent = [0]
    for n in numbers:
        children = []
        for p in parent:
            children.append(p + n)
            children.append(p - n)
        parent = children
    return sum([1 for p in parent if p == target])

kotlin

fun solution(numbers: IntArray, target: Int): Int {
    var parent = mutableListOf(0)
    numbers.forEach { number ->
        val children = mutableListOf<Int>()
        parent.forEach { node ->
            children.add(node + number)
            children.add(node - number)
        }
        parent = children
    }
    return parent.count { it == target }
}