[프로그래머스 Lv2] 타겟 넘버(python)

이진규·2022년 3월 22일
1

프로그래머스(PYTHON)

목록 보기
50/64

문제

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

나의 코드 (답안참조)

"""
1. 아이디어

2. 시간복잡도

"""

def solution(numbers, target):
    
    tree = [0]
    
    for num in numbers:
        
        sub_tree = []
        for node in tree:
            sub_tree.append(node + num)
            sub_tree.append(node - num)
        tree = sub_tree
    
    return tree.count(target)
    

설명

TestCase2 예시의 트리구조는 이렇게 된다.

즉 모든 덧셈을 다 해보고 target의 개수를 찾는 것이다.

수평적으로 더해 한꺼번에 모든 결과값을 얻는 경우로 BFS의 개념이라고 할 수 있음!

참고자료

profile
항상 궁금해하고 공부하고 기록하자.

0개의 댓글