CODING-TEST::타겟 넘버

프로그래머스 타겟 넘버 문제

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

처음엔

1. '-'와 '+'가 들어있는 노드를 각각 만들고
2. 만들어진 노드를 탐색해서 리스트를 만들고
3. 만들어진 리스트에서 값을 추출해 numbers 리스트의 값에 곱하고
	3-1. 곱해진 값의 합을 구하고
4. 합과 target을 비교한다.

였는데

1. '-' => -1, '+' => 1로 변경해서 저장하고
2. ... 나머지는 같음 ...

인 것을

1. 각각 add_depth()가 호출될 때, numbers에서 값을 하나씩 넣어주는 방식으로 바꾸어 트리를 만들 때 계산된 값을 노드의 value로 저장
2. leaf-node의 저장된 value를 target과 비교

하는 형태로 구조를 변경해나갔다.
초기에 사용한 방법부터 yield를 사용했는데, result변수에 자꾸 다른 재귀에서 들어온 값이 누적되는 현상이 발생하여 이를 어떻게 해결할까 고민하다가 copy.deepcopy()로 해결했는데, 시간을 많이 소요하는 함수라서 그런지 시간 초과 오류가 나왔다.

class Node:
    def __init__(self, value) -> None:
        self.value = value
        self.left = None
        self.right = None


class Tree:
    head = None
    depth = -1

    def __init__(self) -> None:
        self.head = Node('start')
        self.depth = 0
        pass

    def add_depth(self, number, depth=0, parent_node=None):
        value = 0
        if not bool(parent_node):
            parent_node = self.head
            value = 0
        else:
            value = parent_node.value

        if not bool(parent_node.left):
            parent_node.left = Node(-1 * number + value)
            parent_node.right = Node(1 * number + value)
            self.depth += 1
            return
        else:
            self.add_depth(number, depth+1, parent_node.left)
            self.add_depth(number, depth+1, parent_node.right)

    def search(self, depth=0, parent_node=None):
        if not bool(parent_node):
            parent_node = self.head

        print(depth, ' : ', parent_node.value)

        if bool(parent_node.left):
            self.search(depth+1, parent_node.left)
            self.search(depth+1, parent_node.right)
        pass

    def search_generator(self, node=None) -> int:
        if not bool(node):
            node = self.head

        if not bool(node.left):
            yield node.value
        else:
            yield from self.search_generator(node.left)
            yield from self.search_generator(node.right)
        pass


def solution(numbers, target) -> int:
    answer = 0

    tree = Tree()

    for num in numbers:
        tree.add_depth(num)

    for result in tree.search_generator():
        if result == target:
            answer += 1

    return answer

실행 결과 코드

numbers = [1, 1, 1, 1, 1]
target = 3

answer = solution(numbers, target)
# print 5
print('answer is ' + str(answer))