[프로그래머스] LV.2 타겟 넘버(python)

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

프로그래머스

 

문제 설명

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 이하인 자연수입니다.

문제 해결

from collections import deque

def solution(numbers, target):
    answer = 0
    result = deque([(0, 0)]) # deque((0, 0)) -> 대괄호를 빼고 선언하면 오류
    while result:
        s, n = result.popleft()
        if n > len(numbers) :
            break
        elif n == len(numbers) and s == target:
            answer += 1
        result.append((s+numbers[n-1], n+1))
        result.append((s-numbers[n-1], n+1))
    return answer

-> 하단의 result.append((s+numbers[n-1], n+1)) 코드에서 처음 n이 0일때 -1을 하게되면 index 상에서 [-1]을 호출한 게 되기때문에 오류가 생기지 않을까 했는데 결국 index가 증가하면서  마지막 index값을 반영하지 않기 때문에 문제 해결 상 모든 인자를 합하거나 뺀 결과가 나와 오류가 생기지 않는다는걸 알았다...

 

문제 풀이 설명

처음 숫자를 더하거나 빼거나 두가지 경우로 나뉘고, 각각 더하고 뺀 경우를 a,b라고 하자.

a와 b가 나온 이후 각 a,b 경우에서 두번째 숫자를 더하거나 빼는 경우가 각각 생긴다.

이 모든 경우의 수를 주어진 매개변수 numbers의 길이만큼 반복하면 target 수와 동일한 숫자를 가진 값들이 나오고,

이 수의 숫자를 answer 에 기록한 뒤 return하면 끝이다.

---

풀이 로직

1. [(0, 0)] # 처음 상태
2. [(1,1), (0,1)] # 길이 1
3. [(0,1), (2,2), (0,2)] # 길이 2 [(1,1), (0,1) 사용]
4. [(2,2), (0,2), (1,2), (-1,2)]
5. [(0,2), (1,2), (-1,2), (3,3), (1,3)] # 길이 3 [(2,2), (0,2), (1,2), (-1,2) 사용]
6. [(1,2), (-1,2), (3,3), (1,3), (1,3), (-1,3)]
7. [(-1,2), (3,3), (1,3), (1,3), (-1,3), (2,3), (0,3)]
8. [(3,3), (1,3), (1,3), (-1,3), (2,3), (0,3), (0,3), (-2,3)]
9. [(1,3), (1,3), (-1,3), (2,3), (0,3), (0,3), (-2,3), (4,4), (2,4)] # 길이 4[(3,3), (1,3), (1,3), (-1,3), (2,3), (0,3), (0,3), (-2,3) 사용]

10. [(1,3), (-1,3), (2,3), (0,3), (0,3), (-2,3), (4,4), (2,4), (2,4), (0,4)]

11. [(-1,3), (2,3), (0,3), (0,3), (-2,3), (4,4), (2,4), (2,4), (0,4), (2,4), (0,4)]

12. [(2,3), (0,3), (0,3), (-2,3), (4,4), (2,4), (2,4), (0,4), (2,4), (0,4), (0,4), (-2,4)]

13. [(0,3), (0,3), (-2,3), (4,4), (2,4), (2,4), (0,4), (2,4), (0,4), (0,4), (-2,4), (3,4), (1,4)]

14. [(0,3), (-2,3), (4,4), (2,4), (2,4), (0,4), (2,4), (0,4), (0,4), (-2,4), (3,4), (1,4), (1,4), (-1,4)]

15. [(-2,3), (4,4), (2,4), (2,4), (0,4), (2,4), (0,4), (0,4), (-2,4), (3,4), (1,4), (1,4), (-1,4), (1,4), (-1,4)]

16. [(4,4), (2,4), (2,4), (0,4), (2,4), (0,4), (0,4), (-2,4), (3,4), (1,4), (1,4), (-1,4), (1,4), (-1,4), (1,4), (-3,4)]

.......

---

# 길이 5 까지 반복하게 되면 sum 값이 target number인 경우의 수가 모두 계산되고, 각 경우의 수당 answer변수를 +1 해준다. (이거 왜 하나하나 계산했지 그냥 print() 해서 붙여넣기 할껄..ㅡㅡ;)