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

문제 링크 - 타겟 넘버(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 이하인 자연수입니다.

입출력 예

numbers	target	return
[1, 1, 1, 1, 1]	3	5
[4, 1, 2, 1]	4	2

문제 풀이

product 를 사용한 중복순열 문제 풀이

from itertools import product

def solution(numbers, target):

temp = [(x, -x) for x in numbers]
#x, -x 아이템을 두개로 다 나눈 뒤 5개의 리스트 전부를 조합한 것이므로 
#(4, -4) (1, -1) (2, -2) (1, -1) 로 이루어질 수 있는 것들 다 만들어주는게 product

    s = list(map(sum, product(*temp)))
    
    for data in s:
    	if data == target:
        	answer += 1
    
    return answer

product 이해 코드

print(list(product(*temp)))
'''
   [(4, 1, 2, 1), (4, 1, 2, -1), (4, 1, -2, 1), (4, 1, -2, -1), (4, -1, 2, 1), (4, -1, 2, -1), (4, -1, -2, 1), (4, -1, -2, -1), (-4, 1, 2, 1), 
   (-4, 1, 2, -1), (-4, 1, -2, 1), (-4, 1, -2, -1), (-4, -1, 2, 1), (-4, -1, 2, -1), 
   (-4, -1, -2, 1), (-4, -1, -2, -1)]
'''
print(s)
'''
[8, 6, 4, 2, 6, 4, 2, 0, 0, -2, -4, -6, -2, -4, -6, -8]
'''

deque를 이용한 bfs풀이

• numbers의 첫 번째 원소에서 얻을 수 있는 경우의 수는 다음 numbers의 +, - 를 붙인 두가지밖에 없다.
  ex.
  1 -> 0
  1 -> 2
  이와 같이 계속 두가지의 경우의 수만 있다고 생각하고 나아가는 BFS 풀이

• index를 붙이고 deque에 넣는 이유는,
  numbers 수를 다 돌았는지 확인 가능하고, 그 이후 target 과 비교해야 하므로 index를 넣는 것이 편하다.

from collections import deque


def solution(numbers, target):
    answer = 0
    
    n = len(numbers)
    queue = deque([])
    
    queue.append([numbers[0], 0])
    queue.append([-1 * numbers[0], 0])
    
    while queue:
        num, idx = queue.popleft()
        idx += 1
        if idx < n:
            queue.append([num + numbers[idx], idx])
            queue.append([num - numbers[idx], idx])
        else:
            if num == target:
                answer += 1
    
    return answer