[Programmers] DFS/BFS > 타겟 넘버

문제. 타겟 넘버

---

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

출처 : 프로그래머스 Level 2 타겟 넘버

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

---

나의 풀이

저는 모든 경우의 수를 찾는 문제라고 생각하여 완전 탐색의 개념으로 문제를 풀어봤습니다. 두 개 이상의 리스트의 모든 조합을 구하는 product를 이용했습니다.

from itertools import product
def solution(numbers, target):
    list_n = [(i,-i) for i in numbers]
    sum_list = list(map(sum, product(*list_n)))
    return sum_list.count(target)

다른 사람의 풀이

#1

def solution(numbers, target):
    num = [0]
    for i in numbers: #1 1 1 1 1
        number = []
        for j in num:
            number.append(j+i) # 1 추가
            number.append(j-i) # -1 추가
        num = number
    return num.count(target)

간단하게 for문과 append를 이용한 bfs 풀이라 가져왔습니다. 구조만 잘 짠다면, 패키지 없이 풀 수 있음을 배울 수 있었습니다.

 

#2

import collections

def solution(numbers, target):
    answer = 0
    stack = collections.deque([(0, 0)])
    while stack:
        current_sum, num_idx = stack.popleft()

        if num_idx == len(numbers):
            if current_sum == target:
                answer += 1
        else:
            number = numbers[num_idx]
            stack.append((current_sum+number, num_idx + 1))
            stack.append((current_sum-number, num_idx + 1))

    return answer

collections의 deque를 이용하여 bfs문을 구현한 코드라 가져왔습니다. 그래프를 탐색할 때 사용하는 대표 알고리즘인 bfs와 dfs는 반드시 공부해야 하는 부분인데요, 아직 익숙하지 않아서 배우고 싶은 마음에 가져왔습니다. deque를 사용하면, 속도적인 면에서 강점이 있으니 익숙해져야 할 것 같습니다.

탐색 알고리즘에 대한 게시물을 작성할 때 자세히 다루겠습니다.