[프로그래머스] 타켓 넘버 - python

문제 정보

문제 유형	난이도	걸린 시간	해결 유무	스스로 구현 성공
DFS/BFS	level2	33m	O	O

 

설계 방법

• numbers 돌면서 arr 모든 요소에 대해 -num과 +num을 해줌
• arr 모든 요소를 돌 때는 arr.popleft()로 하나씩 빼서 사용
• -num과 +num을 해준 요소는 arr.append()
• numbers 다 돌았으면 마지막 arr에 있는 요소 중 target과 일치하는 요소 카운팅

코드

내 풀이

from collections import deque

def solution(numbers, target):
    arr = deque([0])
    for num in numbers:
        for _ in range(len(arr)):
            v = arr.popleft()
            arr.append(v - num)
            arr.append(v + num)
    return arr.count(target)

 

다른 사람 풀이 1

answer = 0
def DFS(idx, numbers, target, value):
    global answer
    N = len(numbers)
    if(idx== N and target == value):
        answer += 1
        return
    if(idx == N):
        return

    DFS(idx+1,numbers,target,value+numbers[idx])
    DFS(idx+1,numbers,target,value-numbers[idx])
def solution(numbers, target):
    global answer
    DFS(0,numbers,target,0)
    return answer

 

다른 사람 풀이 2

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