분할 정복 예제 ( 괄호를 삽입하는 여러가지 방법)

https://leetcode.com/problems/different-ways-to-add-parentheses/

 

 

 

 괄호를 어디에 추가하느냐에 따라 다양한 조합이 가능하다. 모든 조합을 계산해야 하는데 이는 다음 그림과 같이 분할 정복으로 가능하다.

 

 *,-,+ 연산자가 등장할 때 좌/우 분할을 하고 각각 계산 결과를 리턴한다. 분할된 값은 compute() 함수로 계산한 결과를 extend()로 확장한다.

 분할 결과를 리턴받으려면 input이 숫자형일 때 리턴하게 한다.

 

 계산하는 부분은 다음과 같다.

 eval() 함수는 문자열을 파싱하고 파이썬 표현식으로 처리해주는 Evaluate 역할을 한다.

class Solution:
    def diffWaysToCompute(self, expression: str) -> List[int]:
        def compute(left,right,op):
            results=[]
            
            for i in left:
                for r in right:
                    results.append(eval(str(i) +op + str(r)))
            return results
        
        results=[]
        print(expression)
        if expression.isdigit():
            return [int(expression)]
        
        
        for index,value in enumerate(expression):
            if value in "-+*":
                left = self.diffWaysToCompute(expression[:index])
                right=self.diffWaysToCompute(expression[index+1:])
                
                
                results.extend(compute(left,right,value))
                
        return results