Easy is Perfect

[프로그래머스] 타겟 넘버 풀이

  • melonicedlatte
  • Sep 02, 2020


1. 문제

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

2. 풀이

2.1. dfs를 이용한 문제 풀이

  • 아래와 같이 dfs를 이용하여 모든 경우의 수를 전부 체크합니다. 최대 경우의 수가 $ 2^{20} $ 밖에 되지 않아서 쉽게 처리할 수 있습니다.
answer = 0
def dfs(numbers, target, depth, num_sum):
    global answer
    if depth == len(numbers):
        if target == num_sum :
            answer += 1
        return
    dfs(numbers, target, depth + 1, num_sum + numbers[depth]) 
    dfs(numbers, target, depth + 1, num_sum - numbers[depth]) 

def solution(numbers, target):
    dfs(numbers, target, 0, 0)
    return answer

2.2. 재귀를 이용한 풀이

  • 프로그래머스의 숏코딩으로 전역변수를 이용하지 않고 효과적으로 문제를 푼 풀이입니다.
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.3. 곱집합(Cartesian product) 이용한 풀이

# 두 스트링 'ABCD', 'xy' 의 곱집합 : Ax Ay Bx By Cx Cy Dx Dy
import itertools

iterable1 = 'ABCD'
iterable2 = 'xy'
itertools.product(iterable1, iterable2)
  • 곱집합(Cartesian product)에 대한 개념과 예시는 위와 같고, 더욱 더 자세한 설명은 프로그래머스 곱집합 에 나와있습니다.
  • 프로그래머스의 짧은 코드는 아래와 같습니다.
  • itertools 패키지에서 product 함수에 *l 을 이용하여 (-n, n) 형태의 튜플들을 인자로 넣어주면, 아래와 같은 형태의 값을 얻을 수 있습니다.
  • product(*l) 함수를 sum 을 이용하여 값을 모두 더해주고 target과 비교하여 정답을 도출합니다.
list(product(*l))
 
 00 = {tuple: 5} (1, 2, 3, 4, 5)
 01 = {tuple: 5} (1, 2, 3, 4, -5)
 02 = {tuple: 5} (1, 2, 3, -4, 5)
 03 = {tuple: 5} (1, 2, 3, -4, -5)
 04 = {tuple: 5} (1, 2, -3, 4, 5)
 05 = {tuple: 5} (1, 2, -3, 4, -5)
 06 = {tuple: 5} (1, 2, -3, -4, 5)
 07 = {tuple: 5} (1, 2, -3, -4, -5)
 08 = {tuple: 5} (1, -2, 3, 4, 5)
 09 = {tuple: 5} (1, -2, 3, 4, -5)
 10 = {tuple: 5} (1, -2, 3, -4, 5)
 11 = {tuple: 5} (1, -2, 3, -4, -5)
 12 = {tuple: 5} (1, -2, -3, 4, 5)
 ... 

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)

2.3.




Search