프로그래머스 코딩테스트 고득점 Kit_DFS/BFS_타겟 넘버

문제 보러 가기 👈 클릭!

💡 풀이

✔ 내 풀이 방법

• BFS 사용
• queue에 들어있는 시작값은 (0, numbers[0]), (0, -numbers[0]) 2가지 이다. (이때, 0은 인덱스를 의미)
• numbers[0]을 시작으로 다음 리스트 요소를 방문하여 다음리스트요소의 값, 다음리스트요소의값*-1 두가지 숫자를 각각 더하고, 다음 요소의 인덱스가 numbers의 마지막 인덱스보다 이하일경우에 queue에 튜플 (마지막으로 더한 숫자의 인덱스, 총합)를 추가한다.
• 마지막으로 더한 숫자의 인덱스가 numbers의 마지막 인덱스이고, 총합이 타겟 넘버와 같을 때의 개수를 count한다.

from collections import deque

def solution(numbers, target):
    answer = 0
    N = len(numbers)
    
    q = deque([(0, numbers[0]), (0, -numbers[0])])   #(마지막으로 더한 숫자 인덱스, 총합)
    while q:
        idx, sum_num = q.popleft()   
        
        if  idx == N-1 and sum_num == target:
            answer += 1
        
        if idx + 1 < N:
            for num in [numbers[idx+1], -numbers[idx+1]]:
                q.append((idx+1, sum_num+num))
                
    return answer

✔ 다른 풀이 방법

• 재귀를 사용
• 재귀 종료 조건
  1) numbers가 빈 리스트 이고, target넘버가 0 일때 1을 return 하며 종료
  => 해당 경우가 numbers을 더하고 빼서 target넘버를 만드는데 성공
  2) numbers가 빈 리스트 이고, target넘버가 0이 아닐때 0을 return 하며 종료
• numbers[1:] = 현재요소 numbers[0]을 제외한 리스트
  다음 target넘버는 다음과 같이 2가지 이다.
  1) 다음 target = 현재 target - (+numbers[0]) =target - numbers[0]
  2) 다음 target = 현재 target - (-numbers[0]) = target + numbers[0]
• solution( numbers[1:], target - numbers[0])
  + soulution(numbers[1:],target + numbers[0]) 을 return

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