알고리즘 데일리

오랜만에 Divide Conquer 관련 문제를 풀어보았다.

이전에 풀었던 Different Ways to Add Parentheses 참고. (이건 이전 블로그에 푼 방식) 주어진 연산 정보가 있을때 가능한 괄호를 모두 쳐서 연산 결과를 만들면 되는 전형적인 Divide Conquer 문제였다. geeks for geeks에 있는 정답 솔루션은 숫자가 모두 0-9였는데, 문제로 주어진건 두글자 세 글자 이상도 있어서, parsing이 필요하다.

다음과 같이 divide_conquer with memoization을 이용하여 풀 수 있다.

from collections import defaultdict

class Solution:
    def diffWaysToCompute(self, expression: str) -> List[int]:
    	# parsing
        expr = []
        num = ''
        for e in expression:
            if e in ['*', '+', '-']:
                expr.append(num)
                expr.append(e)
                num = ''
            else:
                num += e
        expr.append(num)
        m = defaultdict()

        def divide_conquer(exp, s, e):
            if s == e:
                return [int(exp[s])]
            if e - s == 2:
                return [eval(f'{exp[s]}{exp[s + 1]}{exp[s + 2]}')]
            if (s, e) in m:
                return m[(s, e)]
            # enumerate the position of operator
            res = []
            for i in range(s + 1, e + 1, 2):
                left = divide_conquer(exp, s, i - 1)
                right = divide_conquer(exp, i + 1, e)
                tmp = [eval(f'{l}{exp[i]}{r}') for l in left for r in right]
                res.extend(tmp)
            m[(s, e)] = res
            return res
            
        ans = divide_conquer(expr, 0, len(expr) - 1)
        return sorted(ans)