(python)프로그래머스-타겟넘버

타겟넘버

문제

풀이

첫번째 풀이

DFS 재귀를 사용해서 풀이했다. 정답은 맞추었지만,, -,+를 동시에 재귀로 돌려서 굉장히 복잡하고 비효율적인 코드인 것 같아서 다른 풀이를 보면서 다시 푸는 과정을 진행했다.

def solution(numbers, target):
    answer1 = []
    answer2= []
    r=0
    graph=[[] for i in range(len(numbers))]
    j=1
    for i in range(0,len(numbers)-1):
        graph[i].append(numbers[j])
        graph[i].append(-numbers[j])
        j+=1
    s1=[]
    s1.append(numbers[0])
    s2=[]
    s2.append(-numbers[0])
    count=[0 for i in range(len(numbers)-1)]
    def dfs(k,graph,s,answer,count):
        if graph[k]==[]:
            result=sum(s)
            answer.append(result)
            s.pop()
        else:
            count[k]+=1
            if count[k]==2:
                del s[k:-1]
                count[k]=0
        for i in range(len(graph[k])):
            s.append(graph[k][i])
            dfs(k+1,graph,s,answer,count)
        return answer
    answer1=dfs(0,graph,s1,answer1,count)
    for i in answer1:
        if i==target:
            r+=1
    answer2=dfs(0,graph,s2,answer2,count)
    for i in answer2:
        if i==target:
            r+=1
    return r

DFS

def solution(numbers, target):
    answer = 0
    super_node=[0]
    for num in numbers:
        sub_node=[]
        for sub in super_node:
            sub_node.append(sub+num)
            sub_node.append(sub-num)
        super_node=sub_node
    answer=super_node.count(target)
    return answer

DFS 재귀

answer=0
def DFS(idx,numbers,target,value):
    global answer
    n=len(numbers)
    if (idx==n and target==value):
        answer+=1
        return
    elif 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

BFS

from collections import deque
def solution(numbers, target):
    answer = 0
    q=deque()
    q.append((0,0))
    n=len(numbers)
    while q:
        current_sum,idx=q.popleft()
        if idx==n:
            if current_sum==target:
                answer+=1
        else:
            q.append((current_sum+numbers[idx],idx+1))
            q.append((current_sum-numbers[idx],idx+1))

    return answer