[LeetCode] 241. Different Ways to Add Parentheses

yunan·2021년 2월 21일

leetcode 파이썬알고리즘인터뷰

🐬 알고리즘 풀이 🐬

목록 보기

70/74

🔦 문제 링크

🔊 파이썬 알고리즘 인터뷰 책을 참고했습니다.

문제

숫자와 연산자의 문자열이 주어지면 숫자와 연산자를 그룹화하기 위해 가능한 모든 방법을 계산하여 가능한 모든 결과를 반환합니다. 유효한 연산자는 +,-,*입니다.

✍️ 풀이

분할 정복을 이용해서 문제를 해결해야한다.

분할의 기준은 유효한 연산자가 된다.
분할은 모든 연산자에 대해서 수행되어야 하며 수행되는 순서또한 중요하다.
따라서, 모든 순서에 대해 분할될 수 있도록 각 재귀마다 반복문을 수행한다.

결과는 현 단계에서 나올 수 있는 모든 순서에 대해 계산한 값이다.
이것을 첫번째 재귀가 끝날 때 까지 모두 수행하면 모든 순서에 대한 계산값을 얻을 수 있다.

코드의 주석을 보면서 이해해보자.

🛠 코드

class Solution:
    result = []
    def diffWaysToCompute(self, input: str) -> List[int]:
        def operation(le, ri, oper):
            sm = 0
            result = []
            for l in le:
                for r in ri:
                    if oper == "+":
                        sm = l + r
                    elif oper == "-":
                        sm = l - r
                    elif oper == "*":
                        sm = l * r
                    result.append(sm)
            return result
        results = []
        
        # 연산자없이 오직 숫자만을 가질 때 리스트 형태로 바로 반환.
        if input.isdigit():
            return [int(input)]
        
        # 연산이 수행되는 순서에 따라 값이 달라지므로 모든 경우를 구하기 위해 반복이 필요하다.
        for i in range(len(input)):
            if input[i] in '+-*':
            	# 현재 연산자 기준으로 분할
                left = self.diffWaysToCompute(input[:i])
                right= self.diffWaysToCompute(input[i + 1:])
                
                # 양쪽 결과를 병합해서 나온 값들을 넣어줌
                # 여러 값이 리스트로 나오는 것은 순서마다 나올 수 있는 값이 다르기 때문!
                results.extend(operation(left, right, input[i]))
        return results