leetcode hard : Expression Add Operators

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

Expression Add Operators - LeetCode

 

operator 삽입 문제는 코딩테스트 단골인갑다..

이런문제만 보면 어질어질하다.

 

코드를 보면서 공부해보도록하자.

class Solution:
    def addOperators(self, s: str, target: int) -> List[str]:
        def backtrack(i, path, resultSoFar, prevNum):
            if i == len(s):
                if resultSoFar == target:
                    ans.append(path)
                return

            for j in range(i, len(s)):
                if j > i and s[i] == '0': break
                num = int(s[i:j + 1])
                if i == 0:
                    backtrack(j + 1, path + str(num), resultSoFar + num, num) 
                else:
                    backtrack(j + 1, path + "+" + str(num), resultSoFar + num, num)
                    backtrack(j + 1, path + "-" + str(num), resultSoFar - num, -num)
                    backtrack(j + 1, path + "*" + str(num), resultSoFar - prevNum + prevNum * num, prevNum * num) 

        ans = []
        backtrack(0, "", 0, 0)
        return ans

당연히 노가다 (일명 backtracking) 문제기 때문에

복잡도는 exponential하고 상수조건은 len(s) <= 10로 작게 나왔다.

 

path : 지금까지 operator를 삽입해서 만든 문자열

resultSoFar : 지금까지 계산한 결과값

prevNum : 가장 최근에 만난 숫자

 

핵심은 * 부분에서 resultSoFar - prevNum + prevNum * num인데

A + B * C를 생각해보자.

A + B까지 읽었을 때 resultSoFar = A + B다.

이때 * C를 만나게 되면

resultSoFar( A + B) ) 에서 prevNum (B) 를 빼고 prevNum * num (B * C)를 더하면

(A + B) - B + B * C = A + B * C

이렇게 계산하는 방식이다.

상당히 스마트하군.