Different Ways to Add Parentheses

 

[분할 정복] Different Ways to Add Parentheses

Different Ways to Add Parentheses - LeetCode

 

숫자와 연산자를 문자열로 입력받아 가능한 모든 조합의 결과를 출력하는 문제로 괄호를 어디에 추가하느냐에 따라 다양한 조합과 결과가 가능합니다.  연산자를 만났을 때 Left, Right를 구분하는 분할을 수행하고 연산의 결과를 결합하여최종 결과를 내는 방식으로 풀이하면 됩니다.

 

출처 : https://www.guozet.me/leetcode/Leetcode-241-Different-Ways-to-Add-Parentheses.html

 

 

Solution

class Solution:
    def diffWaysToCompute(self, input: str) -> List[int]:
        #분할 정복
        # 분할 정복은 들어오면 기준점을 잡아서 왼쪽 오른쪽으로 우선 자른다.
        # input="2*3-4*5"
        
        def compute(left, right, op):
            results = []
            for l in left :
                for r in right :
                    results.append(eval(str(l)+ op + str(r)))
                    # print(results, left, right)
            return results
        
        
        if input.isdigit(): #숫자이면
            return [int(input)]
        
        results = []
        
        for index, value in enumerate(input):
            if value in '-*+': # 하나를 기점으로 왼쪽 오른쪽을 나누는 거네
                # 왼쪽 오른쪽을 자르자
                # 왼쪽, 오른쪽 각각의 결과를 받아서 연산하는 것
                left = self.diffWaysToCompute(input[:index])
                right = self.diffWaysToCompute(input[index+1:])
                
                results.extend(compute(left,right, value))
            # print(11, results)
        return results