프로그래머스 - 타겟 넘버 (DFS/BFS)
이번 포스팅에서는 프로그래머스의 타겟 넘버(DFS/BFS) 코딩테스트 연습 문제를 풀어봅니다.
문제 설명
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 |
문제 풀이
n개의 정수가 +, - 2개의 경우의 수로 조합하여 타겟과 일치 여부를 판단합니다. 이에 대한 비교 횟수는 2ⁿ번이 비교 될 수 있도록 제귀함수를 이용하여 구현 하였습니다.
- 숫자가 담긴 리스트를 인자 값으로 전달 받아서 값을 복사 합니다.(깊은 복사 이용)
- 복사한 리스트에서 가장 마지막 요소를 빼서 value에 저장합니다.
- 만일 리스트에 숫자가 남아 있다면 제귀함수를 호출하여 첫번째 인자 값에는 복사한 숫자 리스트, 두번째 인자 값에는 타겟 넘버, 세번째 인자 값에는 sum 값에 value를 더하거나 빼서 2개의 제귀 함수를 호출 합니다.
- 만일 리스트에 숫자가 남아 있지 않으면 마지막 값에 대한 비교 임으로 sum 값에 각각 더하거나 빼서 타겟 넘버와 일치 할 경우 카운트 1을 반환 합니다.
- 이렇게 전달된 카운트 값을 누적하여 방법의 수를 찾아 냅니다.
import copy
# 숫자 조합 제귀 함수
# numbers:숫자가 담긴 리스트, target:목표가 되는 값, 선행 값의 합
def factorial(numbers, target, sum):
count = 0
cns = copy.deepcopy(numbers)
value = cns.pop()
if len(cns): # 리스트의 마지막이 아님으로 제귀함수 호출
count += factorial(cns, target, sum + value)
count += factorial(cns, target, sum - value)
return count
else: # 리스트의 마지막 값임으로 target과 비교
if target == sum+value or target == sum-value:
return 1
else:
return 0
def solution(numbers, target):
answer = factorial(numbers, target, 0)
return answer
print(solution([1, 1, 1, 1, 1], 3))
5
첫번째 풀이때는 위와 같은 방법으로 풀었지만 생각해 보니 타겟 넘버와 합계를 비교 하지 않고 타겟 넘버에서 요소 값을 빼서 0이 되는 값이 타겟과 일치 하는 방법의 수와 같다는 생각이 들었습니다. 그래서 코드를 다음과 같이 수정했습니다.
import copy
# numbers:숫자가 담긴 리스트, target:목표가 되는 값
def solution(numbers, target):
count = 0
cns = copy.deepcopy(numbers)
value = cns.pop()
if len(cns): # 리스트의 마지막이 아님으로 제귀함수 호출
count += solution(cns, target + value)
count += solution(cns, target - value)
return count
else: # 리스트의 마지막 값임으로 target의 값이 0인지 확인
if target + value == 0 or target - value == 0:
return 1
else:
return 0
print(solution([1, 1, 1, 1, 1], 3))
5
따로 함수를 만들지 않고도 solution 함수를 제귀함수로 만들어서 해결이 가능해 졌습니다.
그리고 또 생각하다 보니 깊은 복사 후 리스트에서 제외 해서 값을 전달 하는 방법 외에 제외된 리스트 값을 제귀함수에 전달할 방법이 없을까? 하다가 다음과 같이 다시 수정 하였습니다.
# numbers:숫자가 담긴 리스트, target:목표가 되는 값
def solution(numbers, target):
count = 0
if numbers: # 리스트의 마지막이 아님으로 제귀함수 호출
count += solution(numbers[1:], target + numbers[0])
count += solution(numbers[1:], target - numbers[0])
return count
else: # 리스트의 값이 존재 하지 않음으로 target의 값이 0인지 확인
if target == 0:
return 1
else:
return 0
print(solution([1, 1, 1, 1, 1], 3))
5
단계를 거치면서 정말 코드도 많이 줄고 그 만큼 연산도 많이 줄었습니다. ^^ 앞으로는 효율적인 코드 작성에도 신경을 써야겠네요.
결과는 아래와 같이 잘 통과 되는 것을 확인 할 수 있습니다.
