[프로그래머스] 타겟넘버 ⭕️

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

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

 

문제유형 : DFS/BFS

문제풀이

• 아래 사진처럼 각 노드들은 결과값을 담고있고, 엣지에 각각 +,- 가 붙은 numbers의 원소가 붙게된다.
• 최종적으로 numbers끝까지 계산이 완료됬을경우, 즉 count가 len(numbers)인경우에 해당 노드값 (result)가 target과 같으면 원하는 결과값을 찾았으므로 answer을 1 증가시키도록 한다.
• numbers끝까지 계산되었는데 결과값이 result와 다를경우 dfs를 종료할수 있도록한다.

 

정답코드

# 0에서 시작, +1, -1을엣지에 두고 다음노드는 결과값

def dfs(count, result):
    #마지막노드까지 다 갔을떄 결과가
    global Ganswer
    if count == Glength:
        if Gtarget == result:
            Ganswer += 1
        return

    else:
        dfs(count+1, result+Gnumbers[count])
        dfs(count+1, result-Gnumbers[count])

global Glength, Gtarget, Gnumbers
global Ganswer
def solution(numbers, target):

    global Glength, Gtarget, Gnumbers, Ganswer
    Ganswer = 0
    Gnumbers = numbers
    Glength = len(numbers)
    Gtarget = target

    dfs(0,0)

    return Ganswer

정답코드2 (210706)

def solution(numbers, target):
    
    global result, count
    result = 0
    count = 0
    
    end = len(numbers)
    
    dfs(numbers[0], numbers, 1, target, end)
    result=0
    dfs(-numbers[0], numbers, 1, target, end)
    return count

def dfs(start, graph, depth, target, end):
    global result, count
    result += start
    
    if depth == end:
        if result == target:
            count += 1
        return
    
    next = graph[depth]
    dfs(-next, graph, depth+1, target, end)
    result -= -next
    dfs(next, graph, depth+1, target, end)
    result -= next

 

더 좋은 풀이 (다른사람풀이)

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])

numbers를 차례대로 줄여나가면서 target에 해당 원소값을 빼거나 더해주는식으로 dfs를 진행했는데, dfs함수를 따로 만들지않고 solution자체를 재귀로 돌림

 

만약 numbers원소가 더이상 남아있지 않으면서 (끝남) 값이 target과 같으면 1을 리턴하도록하여 증가시키고

numbers가 끝났는데 target과 같지않으면 0을 리턴해서 값에 변화가 없도록 함...

 

아주 똑똑하시다..