[프로그래머스] 타겟 넘버 Python Code

 

 

프로그래머스 타겟 넘버를 파이썬으로 풀어보겠다.

 

이 문제는 레벨 2로 분류되어 있고

 

DFS, BFS로 풀이할 문제다.

---

문제

 

---

구현

어차피 완전 탐색이지만 BFS에 적응할 겸

BFS로 구현해보겠다.

---

코드

def solution(numbers, target):
    data = [0]
    for num in numbers:
        res = []
        for val in data:
            res.append(val + num)
            res.append(val - num)
        data = res
    
    return data.count(target)

data가 변화하는 flow를 [1,1,1]로 보겠다.

[0] -> [1, -1] -> [2, 0, 0, -2] -> [3, 1, 1, -1, 1, -1, -1, -3]

 

이렇게 변하여 타겟 값이 몇 개인지 확인하면 되는 코드이다.

count를 써도 될 것 같다.

---

다른 풀이

 

dfs 중 좋다고 생각한 코드를 보겠다.

def solution(numbers, target):
    if not numbers and target == 0 :
        return 1
    elif not numbers:
        return 0
    else:
        return solution(numbers[1:], target-numbers[0]) + solution(numbers[1:], target+numbers[0])

처음 값을 target으로 잡고 numbers 리스트를 줄여가며 재귀 호출을 한 코드이다.

 

코드를 보면 이해가 쉽지만 쉽게 생각하기 어려운 방식이다.

 

앞으로 문제를 풀 때 이런 방식을 도입해 봐야겠다.