프로그래머스 43165 타겟 넘버 파이썬 풀이

난이도 : Lv. 2

풀이일 : 2411111

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

프로그래머스

---

문제

---

아이디어

• 모든 숫자에 대해 각 숫자를 빼거나 더한 값을 담아 다음 숫자에 넘겨준다.
• 다음 숫자에서는 넘겨받은 계산 값에 본인을 뺀 값, 더한 값 각각 다음 숫자한테 넘겨준다.
• 마지막 자리의 숫자를 더하거나 뺄 때는 해당 계산이 끝난 후, now가 target과 일치하는지 확인하여 answer 를 더한다.

---

풀이 코드

from collections import deque

def solution(numbers, target):
    answer = 0
    
    queue = deque()
    queue.append((-1, 0))
    
    while queue:
        idx, now = queue.popleft()
        # numbers 마지막 도달 시
        if idx == len(numbers) - 1:
        	# target에 도착했다면 answer + 1
            if now == target:
                answer += 1
            continue
        
        # 현재 숫자를 뺀 값, 더한 값을 각각 큐에 추가
        queue.append((idx + 1, now - numbers[idx + 1]))
        queue.append((idx + 1, now + numbers[idx + 1]))
    
    return answer

• answer : 계산 후, target이 될 수 있는 경우의 수를 센다.
• queue : 현재 까지 계산한 숫자 인덱스와 그 숫자까지 계산한 총계를 담는다.
• queue.append((-1, 0)) : 최초에는 인덱스 -1, 총계 0을 넣고 계산을 시작한다.
• while queue : 큐가 있는 동안 반복해서 idx, now를 확인한다.
• idx : 현재 큐에서 꺼낸 요소가 몇 번째 숫자까지 더해진 결과인지 알려주는 인덱스
• now : idx 인덱스까지 각 요소를 더하거나 빼서 현재까지의 총계
• 만약, now가 target과 일치한다면, target에 도달 할 수 있는 경우의 수를 하나 찾았으므로 answer + 1
• 아직 idx가 가리키는 요소가 마지막 요소가 아니라면, 현재 인덱스와, 현재 인덱스를 넣은 값을 큐에 추가한다.

---

느낀점

• 쉬운 문젠데 딱 보자마자 풀이를 떠올리지 못하고 조금 들여보고 코드를 짰다 왜지?!
• 처음에는 if 문을 and 조건으로 넣어서 인덱스 에러가 발생했다. 코드짜고 고치지 말고 처음부터 잘 짜는 습관을 기르자