🪴 Hayul's digital garden

Search

Search IconIcon to open search

타겟 넘버

Last updated Nov 17, 2022 Edit Source

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 함수를 작성해주세요.

# 제한사항

# 입출력 예

numberstargetreturn
[1, 1, 1, 1, 1]35
[4, 1, 2, 1]42

# 입출력 예 설명

입출력 예 #1

문제 예시와 같습니다.

입출력 예 #2

1
2

+4+1-2+1 = 4
+4-1+2-1 = 4

# 다른 사람 풀이

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

from collections import deque

def solution(numbers, target):
    answer = 0
    queue = deque([(0, 0)])
    while queue:
        current_sum, num_idx = queue.popleft()

        if num_idx == len(numbers):
            if current_sum == target:
                answer += 1
        else:
            number = numbers[num_idx]
            queue.append((current_sum + number, 
            num_idx + 1))
            queue.append((current_sum - number, 
            num_idx + 1))

    return answer

이 풀이의 작동 원리는 이 링크 로 보면 편하게 이해할 수 있다. 이 코드는 breadth-first search( BFS) 알고리즘을 사용한다. BFS는 그래프 수준별로 탐색하는 그래프 탐색 알고리즘의 일종으로, 루트 노드에서 시작하여 다음 수준으로 진행하기 전에 각 수준에서 모든 노드를 확장한다.

이 코드의 시간 복잡도은 그래프의 노드 수와 그래프의 분기 계수에 따라 달라지게 된다. 이 경우 그래프는 숫자 시퀀스로 표시되며 분기 계수는 2가 된다(각 단계에서 대기열에 두 개의 새 노드를 추가하기 때문에). 따라서 이 코드의 시간 복잡도는 $O(2^n)$이며, 여기서 n은 숫자 배열의 길이이다.

# 재귀함수를 써서 풀 수도 있다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

def target_number(numbers, target):
    # Initialize a counter for the number of ways
    ways = 0

    # Recursively try all possible combinations of numbers
    # and check if they add up to the target number
    def find_ways(numbers, index, cur_sum, target):
        nonlocal ways

        # If we have reached the end of the array,
        # check if the current sum is equal to the target
        if index == len(numbers):
            if cur_sum == target:
                ways += 1
            return

        # Try adding the current number to the sum
        find_ways(numbers, index + 1, cur_sum + numbers[index], target)

        # Try subtracting the current number from the sum
        find_ways(numbers, index + 1, cur_sum - numbers[index], target)

    # Start the recursive search from the first number in the array
    find_ways(numbers, 0, 0, target)

    # Return the number of ways
    return ways

This solution uses a recursive function find_ways that tries all possible combinations of numbers in the array and checks if their sum is equal to the target number. At each step, the function has two options: either add the current number to the sum, or subtract it. When the end of the array is reached, the current sum is compared to the target number, and if they are equal, the counter ways is incremented.

이 솔루션은 배열에서 가능한 모든 숫자 조합을 시도하고 합이 목표 숫자와 동일한지 확인하는 재귀 함수 find_ways를 사용합니다. 각 단계에서 함수에는 두 가지 옵션이 있습니다. 즉, 현재 숫자를 합계에 추가하거나 숫자를 빼거나 둘 중 하나입니다. 배열의 끝에 도달하면 현재 합계가 목표 숫자와 비교되고, 둘이 같으면 ways 가 증가합니다.

1
2
3
4
5
6
7
8
9

def solution(numbers, target): 
	def recursive_helper(current_sum, num_idx): 
		if num_idx == len(numbers):
			return 1 if current_sum == target else 0 
		else: 
			number = numbers[num_idx] 
			return recursive_helper(current_sum + number, num_idx + 1) + recursive_helper(current_sum - number, num_idx + 1)

	return recursive_helper(0, 0)

위 방법이 더 명료한 듯 싶다.

Backlinks

Interactive Graph