[프로그래머스 | python] 타겟 넘버

알고리즘 고득점 Kit > 깊이/너비 우선 탐색(DFS/BFS) > 타켓 넘버

 

 

타겟 넘버 Lv.2

n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다.
예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.

사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.



[제한사항]
- 주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
- 각 숫자는 1 이상 50 이하인 자연수입니다.
- 타겟 넘버는 1 이상 1000 이하인 자연수입니다.

 

 

 

첫 번째 풀이 :     100점

def solution(numbers, target):
    answer = 0
    
    q = [[numbers[0], 0], [-1*numbers[0], 0]]
    
    while q:
        temp, now = q.pop()
        now += 1
        
        if now < len(numbers):
            q.append([temp + numbers[now], now])
            q.append([temp - numbers[now], now])
            
        else:
            if temp == target:
                answer += 1
    return answer

• BFS방법
• q에 더하기 빼기한 수와 현재 index 번호(level, label)를 입력
• pop하고 더하기 빼기 한 것을 다시 입력
• 다 pop할 때까지 반복
• pop한 수가 target과 같으면 answer+=1

 

 

 

 

두 번째 풀이:     100점

def solution(numbers, target):
    answer = 0
    
    def dfs(temp, now):
        if now == len(numbers):
            if temp == target:
                nonlocal answer
                answer += 1
            return
        else:
            dfs(temp + numbers[now], now+1)
            dfs(temp - numbers[now], now+1)
        
    dfs(0, 0)
    return answer

• DFS방법
• temp에 현재 숫자를 더하고, 다음 인덱스(=레벨, 레이블)로 넘겨줌

 

 

"변수에 대해서"

• global : 전역 변수
  • global을 앞에 붙이면 함수 밖에서 선언한 전역 함수를 가르키게  
  • 함수 안에서 값을 변경하면 그 값이 출력됨
  • 일반 함수 내에서 전역 변수를 사용할 때 사용

 

• nonlocal : 비지역 변수
  • nonlocal을 앞에 붙이면 함수 밖에서 선언한 비지역 함수를 가르키게 됨
  • 중첩 함수 내에서 상위 함수의 변수를 사용할 때 사용
  • 중첩 함수에서 global을 사용하면 에러남 >> 이럴 때 nonlocal을 사용해줌
  • 위의 문제 같은 경우 프로그래머스는 def로 시작하는 문제 형식이므로 dfs의 중첩 def(함수)를 사용할 경우 nonlocal을 사용해 주어야 함

 

• local : 지역 변수
  • 함수 밖 함수와 다른 지역 함수임을 알림