241 Different Ways to Add Parentheses

• 241 Different Ways to Add Parentheses
  • 문제
  • 조건
  • 예제
  • 해결
    • 1st
      • 1 책 정리
        • extend()
      • 1 코드
      • 1 결과: 성공
    • 2nd
      • 2nd 리트코드 다른 풀이

241 Different Ways to Add Parentheses

문제

Given a string expression of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. You may return the answer in any order.

조건

• 1 <= expression.length <= 20
• expression consists of digits and the operator '+', '-', and '*'.

예제

Input: expression = "2-1-1"
Output: [0,2]
Explanation:
((2-1)-1) = 0 
(2-(1-1)) = 2

Input: expression = "2*3-4*5"
Output: [-34,-14,-10,-10,10]
Explanation:
(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

해결

1st

1 책 정리

• 괄호를 어디에 추가하느냐에 따라 다양한 조합이 가능
• 분할 정복
  • 연산자 기준으로 left, right를 계속 분할하고
  • 분할된 값은 compute()로 계산
  • 계산한 결과는 extned()로 확장

                      |2 x 3 - 4 x 5|
                      │             │
                     ┌┘             └
       |(2) x (3 - 4 x 5)|
              │         │
             ┌┘         └┐
|(3) - (4 x 5)|         |(3 - 4) x (5)|

extend()

• append(): 말 그대로 리스트 내에 추가를 하는 함수
• extend(): 리스트를 확장하는 함수

# list
test = [1, 2, 3]
test.extend(test)
print('test1.extend(test1): {}'.format(test))
test = [1, 2, 3]
test.extend([4,5])
print('[1, 2, 3].extend([4,5]): {}'.format(test))
test = [1, 2, 3]
test.extend([[4,5],[6,7]])
print('[1, 2, 3].extend([[4,5],[6,7]]): {}'.format(test))
test = [1, 2, 3]
test.extend([[[4,5,6]]])
print('[1, 2, 3].extend([[[4,5,6]]])): {}'.format(test))

# tuple
test = [1, 2, 3]
test.extend((1, 2))
print('[1, 2, 3].extend((1, 2)): {}'.format(test))
test = [1, 2, 3]
test.extend(((4, 5)))
print('[1, 2, 3].extend(((4, 5))): {}'.format(test))
test = [1, 2, 3]
test.extend((4, 5, 6))
print('[1, 2, 3].extend((4, 5, 6)): {}'.format(test))
test = [1, 2, 3]
test.extend(((4), (10)))
print('[1, 2, 3].extend(((4), (10))): {}'.format(test))
test = [1, 2, 3]
test.extend(((4, 5), 10))
print('[1, 2, 3].extend(((4, 5), 10)): {}'.format(test))
test = [1, 2, 3]
test.extend(((4, 5), (10)))
print('[1, 2, 3].extend(((4, 5), (10))): {}'.format(test))
test = [1, 2, 3]
test.extend(((4, 5, 6), 10))
print('[1, 2, 3].extend(((4, 5, 6), 10)): {}'.format(test))
test = [1, 2, 3]
test.extend([(4, 5, 6), 10])
print('[1, 2, 3].extend([(4, 5, 6), 10]): {}'.format(test))
test = [1, 2, 3]
test.extend(((4, 5, 6), (10)))
print('[1, 2, 3].extend(((4, 5, 6), (10))): {}'.format(test))
test = [1, 2, 3]
test.extend(((4, 5), (10, 11)))
print('[1, 2, 3].extend(((4, 5), (10, 11))): {}'.format(test))
test = [1, 2, 3]
test.extend(((4, 5, 6), (10, 11, 12)))
print('[1, 2, 3].extend(((4, 5, 6), (10, 11, 12))): {}'.format(test))

# string
test = [1, 2, 3]
test.extend("456")
print('[1, 2, 3].extend("456"): {}'.format(test))
test = [1, 2, 3]
test.extend("abcde")
print('[1, 2, 3].extend("abcde"): {}'.format(test))

'''
test1.extend(test1): [1, 2, 3, 1, 2, 3]
[1, 2, 3].extend([4,5]): [1, 2, 3, 4, 5]
[1, 2, 3].extend([[4,5],[6,7]]): [1, 2, 3, [4, 5], [6, 7]]
[1, 2, 3].extend([[[4,5,6]]])): [1, 2, 3, [[4, 5, 6]]]
[1, 2, 3].extend((1, 2)): [1, 2, 3, 1, 2]
[1, 2, 3].extend(((4, 5))): [1, 2, 3, 4, 5]
[1, 2, 3].extend((4, 5, 6)): [1, 2, 3, 4, 5, 6]
[1, 2, 3].extend(((4), (10))): [1, 2, 3, 4, 10]
[1, 2, 3].extend(((4, 5), 10)): [1, 2, 3, (4, 5), 10]
[1, 2, 3].extend(((4, 5), (10))): [1, 2, 3, (4, 5), 10]
[1, 2, 3].extend(((4, 5, 6), 10)): [1, 2, 3, (4, 5, 6), 10]
[1, 2, 3].extend([(4, 5, 6), 10]): [1, 2, 3, (4, 5, 6), 10]
[1, 2, 3].extend(((4, 5, 6), (10))): [1, 2, 3, (4, 5, 6), 10]
[1, 2, 3].extend(((4, 5), (10, 11))): [1, 2, 3, (4, 5), (10, 11)]
[1, 2, 3].extend(((4, 5, 6), (10, 11, 12))): [1, 2, 3, (4, 5, 6), (10, 11, 12)]
[1, 2, 3].extend("456"): [1, 2, 3, '4', '5', '6']
[1, 2, 3].extend("abcde"): [1, 2, 3, 'a', 'b', 'c', 'd', 'e']
'''

• 튜플을 사용할 때 조금 주의가 필요하다

1 코드

class Solution:
    depth = 0

    def diffWaysToCompute(self, expression: str) -> List[int]:
        self.depth += 1
        def compute(left, right, op):
            results = []
            for l in left:
                for r in right:
                    # print('[{}] {} {} {}'.format(self.depth, l, op, r))
                    results.append(eval(str(l) + op + str(r)))
            if self.depth == 1:
                print()
            return results
        
        if expression.isdigit():
            self.depth -= 1
            return [int(expression)]
        
        results = []
        for idx, op in enumerate(expression):
            if op in '-+*':
                # 연산자 기준으로 좌/우를 나눈다
                left = self.diffWaysToCompute(expression[:idx])
                right = self.diffWaysToCompute(expression[idx + 1:])
                results.extend(compute(left, right, op))
        self.depth -= 1

        return results
'''
[3] 4 * 5
[2] 3 - 20
[3] 3 - 4
[2] -1 * 5
[1] 2 * -17
[1] 2 * -5

[2] 2 * 3
[2] 4 * 5
[1] 6 - 20

[3] 3 - 4
[2] 2 * -1
[3] 2 * 3
[2] 6 - 4
[1] -2 * 5
[1] 2 * 5
'''

1 결과: 성공

Runtime: 68 ms, faster than 13.38% of Python3 online submissions for Different Ways to Add Parentheses.
Memory Usage: 14.5 MB, less than 49.78% of Python3 online submissions for Different Ways to Add Parentheses.

2nd

2nd 리트코드 다른 풀이

def diffWaysToCompute2(self, expression: str) -> List[int]:
    if len(expression) < 2:
        return [int(expression)]
    ans = []
    m = {}
    op = {
        '*': lambda x, y: x * y,
        '-': lambda x, y: x - y,
        '+': lambda x, y: x + y,
    }

    def divideandconquer(s):
        if s in m:
            return m[s]
        left, right, res = [], [], []
        for i in range(len(s)):
            if s[i] in op:  # 연산자인지 여부 확인
                s1 = s[0:i]
                s2 = s[i + 1:]
                left = divideandconquer(s1)
                right = divideandconquer(s2)
                # 책 풀이에서의 `compute`와 같은 역할
                for l in m[s1]:
                    for r in m[s2]:
                        res.append(op[s[i]](l,r)) # 연산자의 람다 식으로 계산
        if not res:
            res.append(int(s))
        m[s] = res
        return res

    ans = divideandconquer(expression)
    return ans

• 분할정복으로 풀이하는 것은 같다
• 람다 식을 미리 정의해두고 사용할 수도 있음