타겟 넘버
시간 제한: 10초
학습 키워드: DFS
문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/43165
문제 설명
n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다.
def solution(numbers, target):
def dfs(idx,total):
if idx==len(numbers):
return 1 if target==total else 0
return dfs(idx+1,total+numbers[idx]) + dfs(idx+1,total-numbers[idx])
return dfs(0,0)코드 설명
코드는 짧고 직관적이므로 별도의 주석을 추가하지 않았다. 문제의 조건은 입력으로 주어진 numbers 리스트의 원소에 부호를 더하거나 빼는 방식으로 값을 탐색하며, 목표 값(target)과 일치하는 모든 경우의 수를 확인하는 것이다. 각 원소는 양수와 음수 두 가지 경우의 수만 존재하기 때문에 시간 복잡도는 O(2^n)이다(여기서 n은 리스트의 길이). 따라서, 입력의 조건을 확인해봐야만 했는데 문제의 입력 길이는 최대 20이기 때문에 시간 복잡도 면에서 큰 부담이 되지 않았다.
이진 트리 구조에서 가지가 뻗어나가면서 numbers의 마지막 원소까지 도달했을 때, 현재까지의 합계가 target 값과 같으면 1을 반환하고, 다르면 0을 반환한다. 각 호출에서 두 가지 경우(현재 원소를 더하거나 빼는 경우)를 재귀적으로 탐색하며, 자식 노드들의 반환 값의 합이 부모 노드로 전달된다. 최종적으로 루트 노드에서 target 값과 일치하는 모든 경우의 수를 반환하게 된다.
코멘트
사실 이 문제는 챌린저 문제가 아니라 미들러 난이도이기 때문에 비교적 수월하게 풀 수 있었다. 챌린저 문제는 퍼즐 조각 채우기(https://school.programmers.co.kr/learn/courses/30/lessons/84021)이고 보자마자 dfs보다 구현에서 굉장히 난이도가 있는 문제라고 느껴져서 미들러 문제로 대체하고 추후에 도전을 해보겠다.
