[프로그래머스/Level2] 타겟 넘버

문제 설명

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

 

입출력 예 설명

문제에 나온 예와 같습니다.

---

나의 풀이

[Python(파이썬)]

def solution(numbers, target):
    from itertools import combinations
    sumlist = sum(numbers)
    a = []

    if (sumlist - target) % 2 == 0:
        minus = int((sumlist - target) / 2)
        for i in range(1, len(numbers)+1):
            a = a + list(combinations(numbers, i))

        for j in range(len(a)):
            a[j] = sum(a[j])
        return a.count(minus)

    else: return 0

---

학습한 내용

나의 풀이 코드를 채점한 결과

나의 풀이로 풀면서 정확성은 맞지만 아무래도 시간적인 면에서 비효율적이지 않을까 생각은 했다.

역시나 문제를 통과는 했지만 테스트 1, 2를 보았을때 시간이 많이 걸렸다. 그래서 더 나은 방법을 학습하기 위해 아래 코드를 보았다. 

# 다른 사람 코드
# 튜플(x, -x), product, map을 이용해서 풀었다. 
from itertools import product
def solution(numbers, target):
    l = [(x, -x) for x in numbers]
    s = list(map(sum, product(*l)))
    return s.count(target)

나는 조합을 사용했지만 위의 코드는 product, 튜플(x, -x), map을 이용하여 풀었다. . 

 

product = 데카르트 곱(cartesian product)

집합 A의 원소 a와 집합 B의 원소 b를 순서대로 벌여 놓고 괄호로 묶은 순서쌍 (a,b) 전체의 집합 

 

위의 다른 사람 코드를 이용해 채점한 결과

 

 

•  파이썬 순열, 조합, product를 학습하여 아래 링크와 같이 정리했다. 

[Python] 순열과 조합

순열 - 서로 다른 n 개 중 r 개를 골라 순서를 고려해 나열한 경우의 수

 

조합 - 서로 다른 n개 중에서 r개(n>=r)취하여 조를 만들 때, 이 하나하나의 조를 n개 중에서 r개 취한 조합 -> 순서 필요 없다. 

 

---

 

문제 출처

코딩테스트 연습 - 타겟 넘버