[코딩테스트/프로그래머스/Python]타겟 넘버

💡생각

• DFS보다 BFS가 수행 시간이 좋으므로 BFS 사용하고 BFS 사용하므로 deque 라이브러리 사용해야겠다고 생각함.
• +숫자일 경우랑 -숫자일 경우를 다 분류해서 타겟 값이 나오는 개수를 세서 리턴해야겠다고 생각함.
• deque으로 구현할 방법이 도무지 떠오르지 않았고 시간이 너무 지나 다른 사람의 코드를 보기로 함.

⏬다른사람의 코드

많은 사람들이 재귀를 사용해서 문제를 풀었지만 재귀보다는 deque을 이용해서 풀고 싶어서 dequed을 사용한 풀이를 찾아 보았음.

🔗풀이 참고
프로그래머스-타겟넘버 질문하기를 참고하였습니다.

rom collections import deque

def solution(numbers, target):
    answer = 0
    queue = deque([(0, 0)]) # sum, level
    while queue:
        s, l = queue.popleft()
        if l > len(numbers):
            break
        elif l == len(numbers) and s == target:
            answer += 1
        queue.append((s+numbers[l-1], l+1))
        queue.append((s-numbers[l-1], l+1))

    return answer

1. 합계와 level이 넣을 deque을 만듦.
2. deque의 왼쪽에서 하나씩 pop해서 합계를 s, level을 l로 지정함.
3. 만약 l이 numbers배열의 길이보다 커지면 반복문을 빠져나감.
4. 만약 l이 numbers배열의 길이와 같고 s가 target과 같아지면 answer에 1을 더함.
5. deque에 s랑 nubers배열의 l-1번째 숫자를 더한 값과 level(l+1)을 append 해주고 s랑 nubers배열의 l-1번째 숫자를 뺀 값과 level(l+1)도 append 해줌.
6. deque이 빌 때까지 반복함.
7. 반복문 빠져나오면 answer값 return.

🔗프로그래머스 - 타겟 넘버
https://programmers.co.kr/learn/courses/30/lessons/43165