[프로그래머스/파이썬] 타겟 넘버 중복순열 풀이 (Python, product, 반복문)

[프로그래머스/파이썬] 타겟 넘버 중복순열 풀이 

(Python, product, 반복문)

 

1. 문제

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

프로그래머스

 

---

2. 문제 해결 아이디어 (풀이)

 

1. 중복순열로 [+.- ]로 이루어진 모든 순열을 구한다.

 

2. 구한 순열을 순회하면서, +/- 를 비교하여 더하거나 빼는 것을 계산한다.

 

3. 결과가 target과 같다면, 결과 +1을 진행한다.

 

---

3. 코드

from itertools import product

# 중복순열 
def solution(numbers, target):
    answer = 0
    array = ['-', '+']
    
    # 1. 중복 순열을 구한다
    products = list(product(array, repeat = len(numbers)))
    
    # 2. 
    for pros in products:
        count = 0
        for i in range(len(pros)):
            if pros[i] == '-':
                count -= numbers[i] 
            elif pros[i] == '+':
                count += numbers[i]
        
        if count == target:
            answer +=1

    
    return answer

** itertools 모듈 product 를 이용하면 중복순열을 구할 수 있다! 

 

 

** DFS 풀이는 아래 게시글에 따로 정리해뒀습니다!

https://raon-2.tistory.com/64

[프로그래머스/파이썬] 타겟 넘버 풀이 (Python, dfs, 재귀함수)

 

---

4. 마무리

해당 방법은 DFS로만 풀 수 있는줄 알았는데, 중복순열을 이용해서 구할수도 있는 점이 신기했다.