프로그래머스에서 풀었던 문제가 마침 leetcode에서 비슷하게 출제되어 푸는김에 같이 정리하는게 나을듯하다.
dfs란?
그림으로 보자면,
마지막 노드까지 전부 확인한 뒤, 이동하는 것을 볼 수 있다.
문제를 보자
문제 설명
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 이하인 자연수입니다.
글로 보니 그래프?가 안떠오를 수 있다. 여러 경우의 수를 그래프로 바꿔보면
이렇게 보면 노란색 부분 경로를 통해 이동할 경우 마지막 값이 문제가 요구하는 target 값으로 나오는 걸 확인할 수 있다.
그럼 구현전에 로직을 정리해보자
- 현재 진행된 순서가 마지막인지 확인한다.
- 아니라면 다음 노드로 연산된 결과를 넘긴다.
- 맞다면 return 1!
- 현재까지 연산된 결과가 target 값인지 확인한다.
- 아니라면 return 0!
코드로 확인해보면,
def dfs(numbers, current_num, target, depth):
if depth == len(numbers): # 현재 진행된 순서가 마지막인지!
if current_num == target: # 현재 연산결과가 target과 같은지!
return 1
else:
return 0
else: # 진행이 아직 남았다면 depth를 늘려 더 깊이 들어가기
depth += 1
return
dfs(numbers, current_num + numbers[depth-1], target, depth) #더하기 부분 노드로 내려가기
+dfs(numbers, current_num - numbers[depth-1], target, depth) #빼기 부분 노드로 내려가기
def solution(numbers, target):
answer = 0
answer = dfs(numbers, 0, target, 0) # 해당 재귀함수 실행!
return answer그림으로 보고, 실제 로직을 구성하고, 해당 로직을 코드로 구현하니 dfs에 대해 좀 더 잘 이해할 수 있었다.
이렇게 푼 이후 leetcode에도 동일한 문제를 발견해 하나 풀어 보았다.
먼저 문제 부터 보자.
282. Expression Add Operators
Hard
Given a string num that contains only digits and an integer target, return all possibilities to add the binary operators '+', '-', or '*' between the digits of numso that the resultant expression evaluates to the target value.
Example 1:
Input: num = "123", target = 6 Output: ["1*2*3","1+2+3"]
Example 2:
Input: num = "232", target = 8 Output: ["2*3+2","2+3*2"]
Example 3:
Input: num = "105", target = 5 Output: ["1*0+5","10-5"]
Example 4:
Input: num = "00", target = 0 Output: ["0*0","0+0","0-0"]
Example 5:
Input: num = "3456237490", target = 9191 Output: []
Constraints:
- 1 <= num.length <= 10
- num consists of only digits.
- 231 <= target <= 231 - 1
target값을 맞추는 건 똑같지만, 이번엔 answer로 몇개가 아닌 해당 target값을 반환하게 한 연산식들을 반환해야 한다.
로직을 살짝 변형 시키면 된다
- 현재 진행된 순서가 마지막인지 확인한다.
- 아니라면 다음 노드로 연산된 결과를 넘긴다.
- 맞다면 return operation_String
- 현재까지 연산된 결과가 target 값인지 확인한다.
- 아니라면 return None
풀면서 주의할 점이 몇가지 존재했다.
- 프로그래머스 문제의 경우 +/- 이기 때문에 순서에 구애받지 않고 값을 연산해 넘겼다. 하지만 *(곱하기) 연산의 경우 연산자 순서가 우선이기 때문에 마지막에 한꺼번에 계산했어야 했다.
- 숫자와 숫자 사이에 연산자가 존재하지 않을 수 도 있었다. 105 → 5의 경우 "10-5" 결과도 나와야 한다.
- 위 조건때문에 "1*05" 같은 경우도 연산식 리스트에 후보로 올라가게 된다. 해당 문제는 걸러낼수 있어야 한다.
- 연산식 스트링을 연산해주는 eval 함수를 사용했는데, 해당 조건의 경우 "00" → "0"으로 알아서 치환해 풀어준다. 문제점은 연산식 스트링에 해당 결과가 포함된다는 것이다. "1+00+5" 같이
위 주의 사항들을 주의 하면서 풀어야 한번에 풀 수 있다. 어떻게 알았냐면
코드로 살펴보자
import re
def dfs(num, depth, target, operation, answer):
if len(num) == depth: #마지막 노드에 도달했는지?
try: # "1+05" 같은 경우 eval 함수 error 발생하므로 try로 제거
if eval(operation) == target: # 연산결과가 target값과 같은지
operation_num_list = re.split("[+*-]",operation)
for op_num in operation_num_list:
#연산자를 제거하고 "00"로 시작하는 문자가 존재하면 잘못된 연산식이므로...
if op_num.startswith("00"):
return
answer.append(operation)
return
else:
return
except:
return
else:
depth += 1
# 분기점을 나눠서 dfs 재귀식 설정
dfs(num, depth, target, operation+"*"+num[depth-1], answer)
dfs(num, depth, target, operation+"+"+num[depth-1], answer)
dfs(num, depth, target, operation+"-"+num[depth-1], answer)
dfs(num, depth, target, operation+num[depth-1], answer)
class Solution:
def addOperators(self, num: str, target: int) -> List[str]:
answer = []
dfs(num, 1, target, num[0], answer) # 재귀식 실행
return answerdfs 알고리즘을 이용해 문제를 풀어보았다.
둘다 재귀를 통해 풀었는데 풀기 전에 하나 유념해야 할 것은 재귀는 depth가 길어질수록 엄청 오래걸리고,
잘못하다가는 stack overflow가 발생할 수 있기 때문에 될 것같은 각일 때만 사용해야 한다.
댓글