241. Different Ways to Add Parentheses

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

 

Difficulty : Medium

 

Status : Solved

 

Time : 00:18:44

 

---

 

문제 설명

 

 

주어진 문자열과 부호로 이루어진 수식을 입력으로 받아, 숫자와 연산자를 그룹화하는 모든 가능한 경우의 수를 계산하여 반환하라. 어떤 순서로 반환하여도 상관 없다.

 

생성된 테스트케이스는 출력값이 32비트 정수 내에 존재하며, 결과의 서로 다른 가짓수는 10^4를 초과하지 않는다.

---

 

풀이

 

처음에는 DP로 풀면서 뭐야, 왜 이렇게 복잡해? 싶었으나.. 내 착각이었다.

 

DP로 풀면 결국 O(N^3)에 가까운 비효율적인 방식의 풀이가 되므로, 조금 다른 접근 방식이 필요하다. (물론 이 문제의 경우 최대 N=20이므로 그다지 차이가 나진 않는다.)

 

풀이 코드 (DP)

class Solution:
    def splitExpr(self, expression: str) -> List[List[str]]: 
        result = [[] for _ in range(2)]
        nums = ''
        for e in expression :
            if e in ['+', '-', '*'] :
                result[0].append(int(nums))
                result[1].append(e)
                nums = ''
            else :
                nums += e
        result[0].append(int(nums))
        return result

    def calculate(self, a:int, b:int, expr: str) -> int:
        if expr == '+' :
            return a + b
        elif expr == '-' :
            return a - b
        return a * b

    def diffWaysToCompute(self, expression: str) -> List[int]:
        expr = self.splitExpr(expression)
        length = len(expr[0])
        dp = [[[] for _ in range(length)] for _ in range(length)]

        for i in range(length) :
            dp[i][i].append(expr[0][i])
        for i in range(1, length) :
            for j in range(length-i) :
                for k in range(j, j+i) :
                    for a in dp[j][k] :
                        for b in dp[k+1][j+i] :
                            res = self.calculate(a, b, expr[1][k])
                            dp[j][j+i].append(res)
        return dp[0][-1]

 

...그럼 다음으로 넘어가서, DP가 아닌 분할 정복을 시도해 보자. 사실 이 방식을 먼저 떠올렸어야 했다.

각각의 expression내의 oprand를 기준으로, 좌측과 우측을 먼저 결과를 생성하고 분할된 결과를 조합하여 연산하면 된다. 생각보다 쉽지 않은가? 그럼 바로 코드를 살펴보도록 하자.

 

 

풀이 코드 (분할정복)

class Solution:
    def calculate(self, a:int, b:int, expr: str) -> int:
        if expr == '+' :
            return a + b
        elif expr == '-' :
            return a - b
        return a * b

    def diffWaysToCompute(self, expression: str) -> List[int]:
        res = []
        for i in range(len(expression)) :
            if expression[i] not in ['+', '-', '*'] :
                continue 
            left = self.diffWaysToCompute(expression[:i])
            right = self.diffWaysToCompute(expression[i+1:])
            expr = expression[i]
            res += [self.calculate(l, r, expr) for l in left for r in right]
        
        if not res :
            res = [int(expression)]
        return res