[코딩 테스트 연습(파이썬/Python)] 프로그래머스 _ 타겟 넘버

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

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

[문제 설명]

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 이하인 자연수입니다.

[아이디어]

1. 전체 합을 기준으로, (-로 바뀔 숫자들의 합)*2를 뺀 숫자가 target인지 확인하면 된다.

2) -로 바뀔 숫자들은 0개부터 n-1개까지 combination으로 탐색하자.

from itertools import combinations
def solution(numbers, target):
    sum_ = sum(numbers)
    cnt = 0
    for i in range(len(numbers)):
        for x in combinations(list(range(len(numbers))), i):
            tmp = 0
            for y in x:
                tmp += numbers[y]*2
            if sum_ - tmp == target:
                cnt +=1
    return cnt

사실 당연히 시간 초과 뜰 것을 감안하고 그냥 돌려봤는데 통과됐다. 하지만 좋은 풀이는 아닌 듯 하다.

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)

가장 문항 의도와 어울리는 풀이인 것 같다.

itertools의 product는 대상들 사이의 가능한 cartesian product(곱집합, 데카르트곱)를 구할 때 사용할 수 있다.

예를 들어, 

위처럼 product(iterable한 객체, repeat = n(default = 1))를 인자로 받아, 객체를 repeat 개수만큼 두고 가능한 모든 cartesian product의 형태를 반환한다. 즉, len(객체)^n의 개수만큼의 결과가 생긴다.

이를 아래처럼 활용할 수 있다.

*(iterable한 객체)를 인자로 넣어주면 특정 후보들을 놓고 가능한 모든 조합을 구하는 데 활용할 수 있다.

# 예시 1
from itertools import product

_list = "abc"
pd = list(product(_list, repeat = 2))
pd

# 예시 2
from itertools import product

_list = ["01", "ab", "XY"]
pd = list(product(*_list))
pd

 

또한 아래는 재귀를 활용한 미띤 풀이,,

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

조합에서의 아이디어와 유사하게, 결국 숫자의 합이 target이 된다는 것은,

1) 맨 앞 숫자를 제외한 나머지 숫자들의 target이 (target - 1번째 숫자) 인 경우

-> 첫 번째 숫자가 + 이면서 target이 완성
2) 맨 앞 숫자를 제외한 나머지 숫자들의 target이 (target + 1번째 숫자) 인 경우

-> 첫 번째 숫자가 - 이면서 target이 완성

 

아래 두 가지 중 하나라는 것을 이용하는 풀이가 되겠다. 위 조건절 두 줄은 재귀의 break를 위한 조건. 재귀가 익숙하지가 않아서 아직은 어렵다,,