[Leetcode] 리트코드 - 괄호를 삽입하는 여러 가지 방법(different-ways-to-add-parentheses) 파이썬(python) 풀이

문제

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

입력 : "2 - 1 - 1"
출력 : [0, 2]
설명
((2 - 1) - 1) = 0
(2 - (1 - 1)) = 2

입력 : "2 * 3 - 4 * 5"
출력 : [-34, -14, -10, -10, 10]
설명
(2 * (3 - (4 * 5))) = -34
((2 * 3) - (4 * 5)) = -14
((2 * (3 - 4)) * 5) = -10
(2 * ((3 - 4) * 5)) = -10
(((2 * 3) - 4) * 5) = 10

코드

"""
fixme. https://leetcode.com/problems/different-ways-to-add-parentheses/
fixme. Q84. 괄호를 삽입하는 여러 가지 방법
fixme. 숫자와 연산자를 입력 받아 가능한 모든 조합의 결과를 출력하라
fixme. 입력 : "2-1-1"
fixme. 출력 : [0, 2]
fixme. 설명
fixme. ((2-1)-1) = 0
fixme. (2-(1-1)) = 2

fixme. 입력 : "2*3-4*5"
fixme. 출력 : [-34, -14, -10, -10, 10]
fixme. 설명
fixme. (2*(3-(4*5))) = -34
fixme. ((2*3)-(4*5)) = -14
fixme. ((2*(3-4))*5) = -10
fixme. (2*((3-4)*5)) = -10
fixme. (((2*3)-4)*5) = 10
"""

from typing import List


class Solution:
    def diffWaysToCompute(self, input: 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 input.isdigit():
            return [int(input)]

        results = []
        for index, value in enumerate(input):
            if value in "-+*":
                left = self.diffWaysToCompute(input[:index])
                right = self.diffWaysToCompute(input[index + 1:])

                results.extend(compute(left, right, value))
        return results

풀이

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

*, -, + 연산자가 등장할 때 좌/우로 분할을 하고 각각 계산 결과를 리턴한다. 2와 3 - 4 * 5에서 3 - 4 * 5는 -17과 -5 복수 개의 계산 결과를 갖게 되며, 최종적으로 2 * [-17, -5] 계산 결과인 [-34, -10]을 리턴하게 된다. 2 * 3과 4 * 5나 2 * 3 - 4와 5처럼 우측에서도 각각 다른 계산 결과도 리턴받게 되며, 최종적으로 [-34, -14, -10, -10, 10] 이렇게 5개 결과를 리턴하게 된다.

class Solution:
    def diffWaysToComputer(self, input: str) -> Li
        results = []
        for index, value in enumerate(input):
            if value in "-+*":
                left = self.diffWaysToCompute(input[:index])
                right = self.diffWaysToCompute(input[index + 1:])

                results.extend(compute(left, right, value))
        return results

연산자를 기준으로 재귀로 left, right를 계속 분할하고, 분할된 값은 compute() 함수로 계산하고, 계산한 결과를 extend()로 확장한다. append() 내장함수가 아닌 extend()를 쓰면 리스트의 원소만 뽑아서 추가할 수 있다.

def diffWaysToCompute(self, input: str) -> List[int]:
    ...
    if input.isdigit():
        return [int(input)]

분할 결과를 리턴받으려면 이처럼 input이 숫자형일 때 리턴하게 한다. 이렇게 하면 분할의 결과가 최종적으로 숫자형인 타입을 재귀의 최종 결과로 리턴하게 될 것이다. 계산을 하는 compute 함수는 다음과 같다.

def compute(left, right, op):
    results = []
    for l in left:
        for r in right:
            results.append(eval(str(l) + op + str(r)))
    return results

eval() 함수는 문자열을 파싱하고 파이썬 표현식으로 처리해주는 역할을 한다. 밑의 그림은 재귀함수를 호출하면서 변수의 흐름이다.

동그라미로 표시된 각각의 재귀함수 호출마다 results = []로 results 리스트를 초기화하여 새롭게 채워나간다. 각각의 재귀함수 호출마다 results에 값이 생기면 그것을 호출한 부모 함수의 left, right로 주어서 진행하게 된다. 그러니깐 결국 2x3-4x5의 for문 안에서의 results만 정답이 된다.

출처
파이썬 알고리즘 인터뷰 (글 : 박상길 그림 : 정진호) [책만]