프로그래머스 - 타겟 넘버

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

Link

문제

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
[4, 1, 2, 1]	4	2

풀이

“정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만드는 방법의 수를 Return”

위 문장에서 내가 생각하는 Key phrase는 3가지다.

• 순서를 바꾸지 않고
• 더하거나 빼서
• 방법의 수를 Return

순서를 지켜야하기 때문에 순서를 무시하는 조합의 문제유형은 아니다.

어떤 수를 더하거나 뺌으로써 경우의 수가 나눠지게 되는데 이때 조건을 만족하는 방법의 수를 Return하는,

즉, 섞지 않고 모든 경우의 수를 탐색하는 DFS/BFS 문제라고 유추할 수 있다.

이중에서도 최단거리를 구하거나 하는 문제가 아니어서 DFS가 제일 적합해보인다.

DFS는 Stack 또는 재귀함수로 구현할 수 있다.

일반적인 처리순서는 아래와 같이 작성할 수 있다.

1. Stack에 starting node인 number[0]를 추가
2. numbers[0]과 연결된, 여기서는 순서를 지켜야하기 때문에 stack.pop()을 하여 numbers[0]에 numbers[1]을 더하거나 뺀 값을 Stack에 추가한다.
3. 2를 반복하여 numbers의 마지막 숫자까지 반복한다.
4. stack안의 값이 없을 때 까지 stack의 값을 pop하면서 target과 같은지 확인하고 카운팅한다.

이를 재귀와 Stack의 코드로 옮기면 아래와 같다.

def solution(numbers, target):
    count = 0
    stack = [[numbers[0], 0], [-numbers[0], 0]]
    
    while stack:
        value, i = stack.pop()

        if value == target and i == len(numbers)-1:
            count += 1
            continue
            
        if i < len(numbers)-1:
            stack.append([value + numbers[i+1], i+1])
            stack.append([value - numbers[i+1], i+1])
        
    return count 

count = 0
def dfs(result, index, numbers, target):
    global count
    if index == len(numbers)-1:
        if result == target:
            count += 1
        return
    dfs(result + numbers[index+1], index+1, numbers, target)
    dfs(result - numbers[index+1], index+1, numbers, target)


def solution(numbers, target):
    global count
    dfs(numbers[0], 0, numbers, target)
    dfs(-numbers[0], 0, numbers, target)
    return count

BFS로도 풀 수 있어 코드를 같이 첨부한다.

참고로 collections 패키지의 deque를 쓰지않으면 시간초과가 난다.

import collections
def solution(numbers, target):
    count = 0
    queue = collections.deque([[numbers[0], 0], [-numbers[0], 0]])
    
    while queue:
        value, i = queue.popleft()
        
        if i < len(numbers)-1:
            queue.append([value + numbers[i+1], i+1])
            queue.append([value - numbers[i+1], i+1])
        elif value == target:
            count += 1

    return count