[ LeetCode - 282 ] Expression Add Operators

https://leetcode.com/problems/expression-add-operators/description/

Expression Add Operators - LeetCode

일반적인 백트래킹(Backtracking) 문제라고 생각했다가 예외 케이스들 덕분에 시간 오래 들였던 문제(일반적인 백트래킹 문제 맞음)

코드 작성은 빠르게 끝냈는데 예외 케이스 하나씩 잡다가 보니까 혼자 삽질하고 있어서 코드 지우고 다시하고를 반복했다...ㅠ

---

[ 📌 풀이 ]

재귀 호출 하면서 expression(식)을 만들고 배열의 마지막 요소까지 갔을 때 만들어진 식을 계산해서 정답에 집어넣는 과정

 

[ ⚙︎ for문 backtracking 호출 ]

1) '*' '+' '-' 3개의 연산자와 다음 숫자를 붙여서 재귀호출한다. ex) 1 '+' 2

 

[ ⚙︎ while문 밑 backtracking 호출 ]

1) 앞의 피연산자의 맨 앞 숫자의 인덱스를 찾아낸다. ex) 1234의 경우 '1'의 인덱스를 first_idx에 저장한다.

2) 찾아낸 인덱스가 가르키는 숫자가 '0'이 아닌 경우 피연산자에 피연산자를 붙인다. ex) '123' 이고 다음 숫자가 '4'면 '1234'로 호출

 

마지막) 배열의 모든 요소에 대해서 식을 만들었다면 결과를 확인해서 target과 같은 값이라면 ans 배열에 삽입한다.

---

[ 📌 막혔던 예외 케이스 ]

• num: "105" / target: 5
  • "10-5": 1과 0을 붙여서 10을 만들어야 했다
• num: "123456789" / target: 45
  • 모든 숫자의 경우의 수를 구해야했음 위의 케이스와 같음
  • 1 / 12 / 123 / 1234 / 12345 / 123456 / 1234567 / 12345678 / 123456789 들에 가능한 모든 연산식을 만들어야함
• num: "1000000009" / target: 9
  • 마찬가지로 1000..... 계속해서 붙였어야함
  • 00이 같이 붙는 케이스는 피해야함

 처음에 나는 예외 케이스를 생각하지 않고 했다가 한 번 틀릴때마다 고쳤는데 이 작업을 반복하다 보니까 코드가 더러워져서 나중에 엉켜서 다시 짤 수 밖에 없었다.

---

[ 📌 코드 - Python ]

class Solution:
    def addOperators(self, num: str, target: int) -> list[str]:
        self.arr = list(map(int, num))
        self.target = target
        self.ans = []

        self.backtracking(1, str(self.arr[0]))

        return self.ans

    def backtracking(self, idx:int, expr:str):
        if idx == len(self.arr):
            if eval(expr) == self.target:
                self.ans.append(expr)
            return
        
        next_num = self.arr[idx]

        for op in ['*', '+', '-']:
            self.backtracking(idx + 1, expr + op + str(next_num))

        first_idx = -1

        while len(expr) >= -first_idx and  expr[first_idx].isdigit():
            first_idx -= 1

        if expr[first_idx + 1] != "0":
            self.backtracking(idx + 1, expr + "" + str(next_num))

---

[ 📌 결과 ]

화면에 다 담지 못할 정도의 실패 횟수...ㄷㄷ

그리고 속도와 메모리의 반비례... (이게 trade off 인가)

[ Result ]