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

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

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

 

DFS/BFS 분류로 되어있지만 문제를 풀 때에는 어떻게 풀어야 할지 참 난감했던 문제다.

 

각 숫자 앞에 -, + 두 가지의 연산자가 올 수 있어 시간복잡도는 최악의 경우 O(2^n)이 나오는데,

 

입력의 수가 최대 20개였기 때문에 그냥 완전탐색으로 시도해 해결했다.

 

from itertools import combinations

def select_index(arridx, array):
    result = []
    for i in range(len(array)+1):
        temp = list(combinations(arridx, i))
        result += temp
    return result

def solution(numbers, target):
    answer = 0
    array_index = []
    indexes = []

    for i in range(len(numbers)):
        array_index.append(i)

    indexes = select_index(array_index, numbers)

    while indexes:
        temp = indexes.pop()
        temp2 = 0
        for i in temp:
            temp2 += numbers[i]
        if sum(numbers) - 2*temp2 == target:
            answer += 1

    return answer

 

다른 사람의 풀이 중 재귀를 이용하는 DFS의 특성을 이용한 풀이와 데카르트 곱을 이용한 풀이가 정말 무릎을 탁 치게 만들었다. 만약 문제가 된다면 삭제하겠읍니다...

 

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])

어떻게 이런 생각을?

 

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

 

 

첫 번째 풀이는 정말 감탄밖에 나오지 않았고 ㅋㅋ;; 두 번째 풀이는 파이써닉함에 감탄했다.

 

데카르트 곱에 대한 내용은 아래 링크에서 확인할 수 있다. 파이썬에서는 itertools 라이브러리의 product 모듈을 import해 사용할 수 있다.

ko.wikipedia.org/wiki/%EA%B3%B1%EC%A7%91%ED%95%A9

곱집합 - 위키백과, 우리 모두의 백과사전

어려운 수식은 넘어가고, 그냥 n개의 집합의 각 원소에 대한 모든 조합을 구한다고 생각하면 된다.