[ Programmers ] level 2 - 타겟 넘버 ( python )

코딩테스트 풀이 

프로그래머스 level 2 문제 

타겟 넘버 - 깊이/너비 우선 탐색(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

문제 풀이 

 

 말 그래도 DFS를 이용하는 문제이다. 깊이 우선 탐색으로 생각하면 쉽다. 

 

문제 풀면서 항상 생기는 문제는 역시 문제를 제대로 이해하는 가 인것 같다...

예시에 1만 있어서 어떻게 풀어야 하는지 헷갈렸다... 차라리 1,2,3,4,5 이런 식의 예가 있는 것이 더 이해하기 쉬울 것ㄱ 같다. 

효율성을 충족하기는 했으나 별 로 효율적이라고는 잘 모르겠다.. 

def solution(numbers, target):
    sup= [0]
    for i in numbers:
        sub = []
        for j in sup : 
            sub.append(j+i)
            sub.append(j-i)
        sup = sub
    return sup.count(target)

위의 넓이 우선 탐색을 이용한 것이라고 보면 이해하기 쉽다.

먼저 super node로 [0]을 하나 만들어 두고 

[0+1] [0-1] 로 sub node 두개를 생성한다

이렇게 생성된노드 super node로 저장되고, 

저장된 super node는 for문을 돌면서 [0+1+1] [0+1-1] , [0-1+1] [0-1-1] 를 거치면서 super node에 다시 저장된다.

 

이런 방식으로 전체 저장되는 리스트가

[5, 3, 3, 1, 3, 1, 1, -1, 3, 1, 1, -1, 1, -1, -1, -3, 3, 1, 1, -1, 1, -1, -1, -3, 1, -1, -1, -3, -1, -3, -3, -5]

이 되고 여기에서 target number인 3의 개수를 count 로 찾으면 된다. 

이 문제는 조금 예시가 부족하다는 생각이 든다!