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

문제

n개의 음이 아닌 정수들이 있다.

이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만드려고 한다.

 

예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있다.

1. -1+1+1+1+1 = 3

2. +1-1+1+1+1 = 3

3. +1+1-1+1+1 = 3

4. +1+1+1-1+1 = 3

5. +1+1+1+1-1 = 3

 

사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때

숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 경우의 수를 반환하는 함수를 만들어야 한다.

 

 

제한사항

1. 주어지는 숫자의 개수는 2개 이상 20개 이하이다.

2. 각 숫자는 1 이상 50 이하인 자연수이다.

3. 타겟 넘버는 1 이상 1,000 이하인 자연수이다.

 

 

코드

# DFS
def solution(numbers, target):
    def DFS(numbers, target, depth):
        answer = 0
        if depth == len(numbers):
            if sum(numbers) == target:
                return 1
            else:
                return 0
        else:
            answer += DFS(numbers, target, depth+1)
            numbers[depth] *= -1
            answer += DFS(numbers, target, depth+1)
            return answer
    
    answer = DFS(numbers, target, 0)
    return answer

# BFS
def solution(numbers, target):
    answer = 0
    leaves = [0]
    for num in numbers:
        tmp = []
        for parent in leaves:
            tmp.append(parent + num)
            tmp.append(parent - num)
        leaves = tmp
    
    for leaf in leaves:
        if leaf == target:
            answer += 1
    
    return answer

 

 

설명

문제 이해는 쉬운데

어떻게 풀 지 모르겠어서 다른 사람의 풀이를 참고했다.

 

DFS, BFS를 사용해서 모든 경우의 수를 만들어 타겟 넘버가 되는 경우를 체크한다.

 

DFS부터 설명한다.

def DFS(numbers, target, depth):
	answer = 0
	if depth == len(numbers):
		if sum(numbers) == target:
			return 1
		else:
			return 0
	else:
		answer += DFS(numbers, target, depth+1)
		numbers[depth] *= -1
		answer += DFS(numbers, target, depth+1)
		return answer

DFS를 구현한 함수이다.

 

if depth == len(numbers):
	if sum(numbers) == target:
		return 1
	else:
		return 0

재귀함수의 종료조건이다.

현재 depth가 numbers배열의 길이와 같다면 현재 numbers배열의 총합과 target을 비교하여

같다면 1을 다르다면 0을 반환한다.

 

else:
	answer += DFS(numbers, target, depth+1)
	numbers[depth] *= -1
	answer += DFS(numbers, target, depth+1)
	return answer

depth가 아직 numers배열의 길이와 같지 않다면 아래의 동작을 한다.

1. depth를 1 늘리고 재귀한다.

2. 현재 depth 위치의 numbers 배열의 원소의 부호를 바꾼 뒤 depth를 1 늘리고 재귀한다.

 

계산된 answer를 반환한다.

 

answer = DFS(numbers, target, 0)
return answer

DFS 함수를 사용해서 원하는 answer를 찾는다.

answer를 반환한다.

 

코드만 보면 이해하기 어려워서 간단한 예시와 그림으로 설명을 추가한다.

 

numbers 배열이 [3, 3, 1]이고 target이 5라고 가정하자.

DFS함수는 재귀하면서 아래와 같은 그래프를 만들 것이다.

 

depth가 0에서 1로

 

depth가 1에서 2로

depth가 numbers배열의 길이와 같아졌을 때 재귀함수는 종료조건을 만족하여

그 조건에 맞는 동작을 진행한다.

 

종료

각각의 상태에서의 numbers배열의 총합을 확인한다.

 

sum(numbers)들

 

answer들

numbers배열의 총합이 target과 같다면 1을 그렇지 않다면 0을 반환한다.

 

재귀가 종료되면 위 과정으로 answer가 기록되어 원하는 결과를 얻을 수 있다.

 

 

이번에는 BFS 코드를 설명한다.

 

def solution(numbers, target):
    answer = 0
    leaves = [0]
    for num in numbers:
        tmp = []
        for parent in leaves:
            tmp.append(parent + num)
            tmp.append(parent - num)
        leaves = tmp
    
    for leaf in leaves:
        if leaf == target:
            answer += 1
    
    return answer

 

leaves = [0]
for num in numbers:
	tmp = []
	for parent in leaves:
		tmp.append(parent + num)
		tmp.append(parent - num)
	leaves = tmp

numbers 배열의 숫자를 꺼내며 반복한다.

현재 leaves 배열에 있는 원소와 num을 더하여 tmp에 저장한다.

안쪽 반복이 끝나면 leaves 배열을 tmp로 교체한다.

 

for leaf in leaves:
	if leaf == target:
		answer += 1

leaves 배열의 원소들을 하나씩 꺼내며 반복한다.

leaf가 target과 같다면 answer에 1을 더한다.

 

return answer

answer를 반환한다.

 

BFS는 DFS에 비해서 조금은 이해하기가 쉬워보인다.

마찬가지로 그림과 설명을 추가한다.

 

BFS 코드는 

부모 층의 값들에 numbers배열의 num을 부호를 바꿔 더해 자식 층을 만드는 동작을 한다.

 

이번에도 numbers = [3, 3, 1], target = 5의 상황을 가정하고 설명한다.

첫번째 반복

 

두번째 반복

 

마지막 반복

마지막 반복이 끝나면 현재 leaves배열은 [-7, -5, -1, 1, -1, 1, 5, 7]로 초기화되어 있을 것이다.

이 배열에서 target과 같은 수를 체크해서 개수를 세면 원하는 정답을 얻게 된다.

---

참고 링크1 : https://velog.io/@timointhebush/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%ED%83%80%EA%B2%9F-%EB%84%98%EB%B2%84-DFS-BFS-Python

프로그래머스 - 타겟 넘버 (DFS, BFS) Python

 

참고 링크2:

이 글쓴이는 문제를 아주 간단하게 풀었는데, 나는 이해가 잘 안되서 사용하지는 않았다.

이해만 잘 한다면 이 쪽의 코드가 훨씬 좋아보인다.

https://bomoto.tistory.com/60?category=933451