Algorithm

타겟 넘버

Algorithm

문제 설명

n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.

1
2
3
4
5
-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

입출력 예 설명

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

나의 풀이

1
2
3
4
5
6
7
8
9
10
11
12
13
14
numbers = [1,1,1,1,1]
target = 3

from itertools import combinations
def solution(numbers, target):
    total = 0
    for i in range(1,len(numbers)+1):
        for j in combinations(range(len(numbers)),i):
            num = numbers.copy()
            for z in j:
                num[z]=-num[z]
            if sum(num) == target:
                total += 1
    return total

다른 사람의 풀이

1
2
3
4
5
6
7
8
9
def solution(numbers, target):
    # number가 비어있고, target 이 0이면 1을 리턴해라
    if (not numbers) and (not target):
        return 1
    # number가 비어있고 target 이 0이 아니면 0을 리턴해라
    elif not numbers: 
        return 0
    else:
        return solution(numbers[1:], target-numbers[0]) + solution(numbers[1:], target+numbers[0])

위와 똑같은 코드를 lambda 함수로 구현

1
2
3
4
solution = lambda numbers, target: 1 \
if not numbers and target == 0 \
else 0 if not numbers \
else solution(numbers[1:], target - numbers[0]) + solution(numbers[1:], target + numbers[0])

Python Combinations & Permutation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from itertools import permutations
from itertools import combinations

perm = permutations([1,2,3])
for i in perm:
    print(i)
# (1, 2, 3)
# (1, 3, 2)
# (2, 1, 3)
# (2, 3, 1)
# (3, 1, 2)
# (3, 2, 1)

comb = combinations([1,2,3],2)
for i in comb:
    print(i)
# (1, 2)
# (1, 3)
# (2, 3)

Combinations Functions Structures

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def combinations(iterable, r):
    # combinations('ABCD', 2) --> AB AC AD BC BD CD
    pool = tuple(iterable)
    n = len(pool)
    if r > n:
        return
    indices = list(range(r))
    yield tuple(pool[i] for i in indices)
    while True:        
        for i in reversed(range(r)):
            if indices[i] != i + n - r:
                break
        else:
            return
        indices[i] += 1
        for j in range(i+1, r):
            indices[j] = indices[j-1] + 1
        yield tuple(pool[i] for i in indices)

위의 코드를 이해하자. 생소한 for ~ else 구문도 이해하고 넘어가기.

Share