programmers- lv.2 (타겟 넘버)

문제링크: 타겟 넘버

✍🏻 Information

	content
언어	python
난이도	⭐️⭐️⭐️
풀이시간	45분
제출횟수	1
인터넷검색유무	yes

🍒 My Code

from itertools import combinations
def solution(numbers, target):
    answer = 0
    minus_numbers = [-i for i in numbers]
    all_idx = [i for i in range(len(numbers))]
    for i in range(1,len(numbers)+1):
        c = list(combinations(all_idx,i))
        for j in c:
            plus_idx=list(j)
            minus_idx=list(set(all_idx)-set(j))
            SUM = sum([numbers[k] for k in plus_idx])+sum([minus_numbers[k] for k in minus_idx])
            if SUM==target:
                answer+=1
    return answer

💡 What I learned

• 좋다고 생각한 풀이
  <풀이1>

def solution(numbers, target):
    if not numbers and target == 0 :
        return 1
    elif not numbers:
        return 0
    else:
        return solution(numbers[1:], target-numbers[0]) + solution(numbers[1:], target+numbers[0])

<풀이2>

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)

▶️ 두개 이상의 리스트에서 모든 조합 구하기 : list(product(*items))
참고 : https://ourcstory.tistory.com/414

from itertools import product

items = [['a', 'b', 'c,'], ['1', '2', '3', '4'], ['!', '@', '#']]
list(product(*items))

# [('a', '1', '!'), ('a', '1', '@'), ('a', '1', '#'), ('a', '2', '!'), ('a', '2', '@'), ('a', '2', '#'), ('a', '3', '!'), ('a', '3', '@'), ('a', '3', '#'), ('a', '4', '!'), ('a', '4', '@'), ('a', '4', '#'), ('b', '1', '!'), ('b', '1', '@'), ('b', '1', '#'), ('b', '2', '!'), ('b', '2', '@'), ('b', '2', '#'), ('b', '3', '!'), ('b', '3', '@'), ('b', '3', '#'), ('b', '4', '!'), ('b', '4', '@'), ('b', '4', '#'), ('c,', '1', '!'), ('c,', '1', '@'), ('c,', '1', '#'), ('c,', '2', '!'), ('c,', '2', '@'), ('c,', '2', '#'), ('c,', '3', '!'), ('c,', '3', '@'), ('c,', '3', '#'), ('c,', '4', '!'), ('c,', '4', '@'), ('c,', '4', '#')]

<풀이3>

def solution(numbers, target):
    q = [0]
    for n in numbers:
        s = []
        for _ in range(len(q)):
            x = q.pop()
            s.append(x + n)
            s.append(x + n*(-1))
        q = s.copy()
    return q.count(target)

• 나 너무 시간복잡도 높게 짬.. dfs 써서 다시 풀어볼것(이것도 시간복잡도는 높지만 연습하는 느낌으로)