[Programmers] 타겟 넘버 (Python3)

문제

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

입출력 예

|numbers| target| return|
|:—:|:—:|:—:|
|[1, 1, 1, 1, 1] |3 |5|

입출력 예 설명

문제에 나온 예와 같습니다.

문제풀이

제한사항에 주어진 개수와 경우의 수가 매우 적어서 그냥 브루트포스로 combinations를 이용하여 모든 조합을 찾아서 답을 찾았다. 브루트포스로 푼다는 가정하에 combinations 메서드만 알면 난이도가 낮은 문제인 것 같다.

코드

from itertools import combinations

def solution(numbers, target):
    result = 0
    for i in range(len(numbers)):
            combi = list(combinations([i for i in range(len(numbers))],i))
            for com in combi:
                change_num = numbers.copy()
                
                for idx in com:
                    change_num[idx] = -change_num[idx]
                if sum(change_num) == target:
                    result+=1           
    return result

solution([1,1,1,1,1], 3)

5

노트

사실 브루트포스로 그냥 풀겠다고 마음먹을 때부터 100명중에 50등 정도하는 코드라고 생각하긴 했는데, 100명중에 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])

그러고보니까 이 문제의 분류가 dfs/bfs로 되어있었다.
그래서 나도 처음에는 dfs/bfs로 생각하다가 잘 안풀리길래, 제한사항 경우의 수를 보니 시간적합도 남아 돌겠다 싶어서 브루트포스로 풀어버렸다.

타겟넘버가 dfs/bfs 문제인 이유는 다음인덱스에 해당하는 numbers 원소를 더하거나 뺀값을 새로운 노드로 모두 생성해주고, 그 값로 만든 새로운 그래프에 하나씩 방문하면서 numbers의 합이 같을때마다 count해주면 되기 때문이다.

그래서 저 위 코드는 numbers에 존재하는 값을 target에다가 더하거나 빼서 target이 0이 나오면 1을 리턴하고 0이 아니면 0을 리턴한 후, numbers를 그 다음요소부터 [1:]로 인덱싱하여 재귀함수로 다시 solution을 호출하는 방식으로 numbers의 요소를 각각 +,-로 바꿔가며 계산하여 풀었다.

사실 보다보니까 음수가 난 여러개인 경우의 수도 있다고 생각했는데, 사실 답은 음수는 무조건 하나여서 문제 설명이 좀 부족한게 아닌가 하는 생각이 들었다. 예제를 더 주던지, 제한사항을 추가해야할듯…