[프로그래머스] 타겟 넘버 (Level 2) (파이썬 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 이하인 자연수입니다.

 

입출력 예

 

numbers / target / return

[1, 1, 1, 1, 1]	3	5
[4, 1, 2, 1]	4	2

 

입출력 예 설명

 

입출력 예 #1

 

문제 예시와 같습니다.

 

입출력 예 #2

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

총 2가지 방법이 있으므로, 2를 return 합니다.

 

 

 

문제 풀이

 

DFS와 BFS를 활용하여 푸는 문제인데, 세 가지 방법을 통해 풀이해봐야겠다.

 

 

1) DFS - 재귀함수

 

answer = 0


def DFS(i, numbers, target, num):
    global answer
    N = len(numbers)
    if i == N and target == num:
        answer += 1
        return
    if i == N:
        return

    DFS(i + 1, numbers, target, num + numbers[i])
    DFS(i + 1, numbers, target, num - numbers[i])


def solution(numbers, target):
    global answer
    DFS(0, numbers, target, 0)
    return answer


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

 

DFS 중 재귀함수를 이용한 방법이다

인덱스와 값을 계속적으로 검사하여 인덱스가 제공된 리스트의 값과 같고(모든 숫자를 사용해야하므로)

타겟값과 현재 값이 같으면 answer에 1을 추가해준다.

자식 노드로 넘어갈 때마다 인덱스는 1씩 증가되며,

자식노드로는 numbers의 다음 인덱스의 해당하는 값이 +되거나 -되는 경우가 있으므로

기존 값에 +numbers[idx], -numbers[idx]를 해주는 것이다.

이 과정을 반복하기 위해 재귀함수로 작성한다.

 

 

2) DFS - 스택

 

def solution(numbers, target):
    answer = 0
    stack = []
    length = len(numbers)
    stack.append([-numbers[0], 0])
    stack.append([numbers[0], 0])

    while stack:
        num, i = stack.pop()
        if i + 1 == length:
            if num == target:
                answer += 1
        else:
            stack.append([num - numbers[i + 1], i + 1])
            stack.append([num + numbers[i + 1], i + 1])

    return answer

 

DFS를 구현하는 방법 중 스택을 이용한 방법이다.

while문에 들어가야하므로 먼저 stack 안에 numbers의 0번 노드 값을 -한 값, +한 값을 기본으로 넣어준다.

이제 스택의 원리로 하나씩 pop하면서 자식 노드값을 불러와 다시 stack에 넣어주는 것이다!

이때 인덱스 검사를 위해 리스트의 두 번째 값에 인덱스를 1씩 증가시켜 넣어준다.

위 재귀함수 코드에서는 인덱스가 0일 때 아무값도 넣지 않아 1번 인덱스부터 값이 들어갔다.

그렇기 때문에 검사를 할 때 i == N으로 표현되었지만,

이 코드에서는 0번 인덱스부터 값이 들어갔기 때문에

if i + 1 == length로 검사를 해주었다

(stack.append([-numbers[0], 0])을 해줄 때 인덱스를 애초에 1로 넣어주고 if문에서 i로 넣어줘도 되겠다)

인덱스가 numbers의 길이와 다를 경우 어차피 모든 숫자를 사용하는 조건을 만족하지 못하므로

else로 빠져나가 다음 자식 노드들을 stack에 넣어주고 만족할 경우 

현재 숫자와 타겟 넘버가 같은지 검사한 후 같을 경우 answer에 1을 더해준다.

 

 

3) BFS

 

from collections import deque

def solution(numbers, target):
    answer = 0
    queue = deque()
    length = len(numbers)
    queue.append([-numbers[0], 0])
    queue.append([numbers[0], 0])

    while queue:
        num, i = queue.popleft()
        if i + 1 == length:
            if num == target:
                answer += 1
        else:
            queue.append([num - numbers[i + 1], i + 1])
            queue.append([num + numbers[i + 1], i + 1])

    return answer

 

 

DFS와 비슷하지만 큐를 사용했다.

결과에 대해서는 어차피 정답의 개수만 나오기 때문에 차이가 없다.

중간에 노드를 추가하는 과정에서 순서의 차이만 생긴다.