84. Different Ways to Add Parentheses

리트코드

• 숫자와 연산자를 입력받아 가능한 모든 조합의 결과를 출력하라

1. 분할 정복을 이용한 다양한 조합

class Solution:
    def diffWaysToCompute(self, expression: str) -> List[int]:
        
        def compute(left, right, op):
            results = []
            
            for l in left:
                for r in right:
                    results.append(eval(str(l) + op + str(r)))
                
            return results
        
        if expression.isdigit():
            return [int(expression)]
            
        results = []
        
        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

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

  

  • *, -, + 연산자가 등장할 때 좌/우 분할을 하고 각각 계산 결과를 리턴한다.

  • 3-4*5과 -17과 -5 복수 개의 계산 결과를 갖게 되며, 최종적으로 2 * [17, -5] 계산 결과인 [-34, -10]을 리턴하게 된다.

  • 생략되었지만 우측으로는 각각 다른 계산 결과도 리턴받게 되며, 최종적으로는 [-34, -14, -10, -10, 10] 이렇게 5개 결과를 리턴하게 된다.

• 연산자를 기준으로 재귀로 left, right를 계속 분할하고, 분할된 값은 compute() 함수로 계산한 결과를 extend()로 확장한다.

  • append()는 리스트 전체를 또 다른 엘리먼트로 처리

    [1,2,3,[4,5]]

  • extend()는 삽입 대상의 리스트를 풀어서 각각의 엘리먼트로 확장해 삽입한다.

    [1,2,3,4,5]

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

  • 이렇게 하면 분할의 결과가 최종적으로 숫자형인 타입을 재귀의 최종 결과로 리턴하게 될 것이다.

• 그림에서 마지막 계산 직전에 right는 [-17, -5]가 된다.

  • 이 처럼 복수형일 수도 있기 때문에, 각각 반복으로 단수형 값을 추출해 계산한다.

  • 리스트 컴프리헨션으로 처리할 수 있지만, 가독성을 높이기 위해 풀어서 작성한다.

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