LeetCode #241 Different Ways to Add Parentheses

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

문제 링크

LeetCode #241 Different Ways to Add Parentheses

문제 풀이

주어진 연산식에 괄호를 삽입할 수 있는 모든 경우의 수에 대해 삽입하고 그에 대한 연산 결과를 리턴해야 한다. 여기서 알 수 있는 점은 주어진 연산자가 +, -, * 밖에 없으므로 0으로 나누는 결과를 고려할 필요가 없다.

분할 정복으로 해결할 수 있는데 몇 가지 생각이 필요하다. 우선 괄호를 어떻게 놓아서 분할하느냐의 문제다. 이에 대해 재귀 호출로 연산자를 기점으로 나눠 좌우측으로 구분하고 분할된 부분이 단순 숫자일 경우 최소 단위에 도달함을 의미하므로 그대로 리턴한다. 리턴된 결과값들을 연산자로 계산하여 다시 그 결과값을 리턴한다. 이 과정을 모든 글자에 대해 순회하면 모든 경우의 수에 대해 탐색할 수 있겠다.

• 리턴할 결과값들을 저장할 리스트 생성
• 각 글자에 대해 iterate
• 만약 탐색 좌표의 글자가 +, -, * 중 하나로 연산자에 해당된다면 연산자를 기준으로 좌/우측으로 나누어 재귀 호출 (분할)
• 만약 입력이 단순 숫자라면 그대로 리턴 (부분 문제의 최소 단위)
• 리턴 받은 좌, 우측 결과에 대해 연산자를 적용하여 계산 (eval 연산, 정복)
• 맨 처음 호출위치까지 리턴받아 종료

python 코드

class Solution:
    def compute(self, l1, l2, exp):
        result = []
        for i in l1:
            for j in l2:
                result.append(eval(str(i) + exp + str(j)))
        return result
    def diffWaysToCompute(self, expression: str):
        if expression.isdigit():
            return [expression]
        result = []
        for i, exp in enumerate(expression):
            if exp in "+-*":
                left = self.diffWaysToCompute(expression[:i])
                right = self.deffWaysToCompute(expression[i + 1:])
                result.extend(self.compute(left, right, exp))
        return result