[LeetCode] 241. Different Ways to Add Parentheses

📃 문제 설명

(MEDIUM) https://leetcode.com/problems/different-ways-to-add-parentheses/

• 주어진 계산식을 일반적으로 통용되는 계산 순서를 무시하고 계산할 수 있는 모든 값들을 출력하는 문제이다.

Example 1:

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

Example 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

🔎 문제 접근

• 주어진 expression이 string이기에 number와 operator으로 먼저 parsing하는 logic을 구현했다.
  • expression의 모든 character에 대해 '+', '-', '*'가 나왔을 때, 이전의 문자열을 number, 현재의 character을 operator로 인식, list에 추가해주었다.
  • 맨 마지막 number는 operator가 나오지 않아 list에 추가되지 않았기에, 따로 계산해 list에 추가해줬다.
• 초반에는 해당 expression에 등장하는 모든 operator를 나열해 순서대로 계산하면 되지 않을까라는 생각을 했다. 예컨데, 9개의 operator가 있고 이를 각각 0, 1, ... , 8이라 한다면 0부터 8까지 나열할 수 있는 모든 가짓수 에 대해 계산하는 것이다.

class Solution:
    def diffWaysToCompute(self, expression: str) -> List[int]:
        # 주어진 expression 문자열을 number와 operator로 parse하는 과정
        expressionList = []
        
        num_st, num_end = 0, 0
        while num_end < len(expression):
            if ord('0') <= ord(expression[num_end]) <= ord('9'):
                num_end += 1
                continue
            
            expressionList.append(int(expression[num_st:num_end]))
            expressionList.append(expression[num_end])
            
            num_st = num_end = num_end + 1
        
        if num_st > 0:
            expressionList.append(int(expression[num_st:]))
        
        # 주어진 숫자와 operator를 바탕으로 계산
        def calcOperation(firstNum, operation, secondNum):
            if operation == '+':
                return firstNum + secondNum
            elif operation == '-':
                return firstNum - secondNum
            else:
                return firstNum * secondNum
        
        ans = set()
        def selectOperation(expressionList):
        	# 주어진 expressionList가 3일 경우 계산된 값을 ans에 추가
            if len(expressionList) == 3:
                ans.add(calcOperation(expressionList[0], expressionList[1], expressionList[2]))
                return
            
            # expressionList 내의 모든 operator에 대해 반복 작업
            for idx in range((len(expressionList) - 1) // 2):
                # tmp: 선택된 operator의 계산 결과를 포함한 새로운 expressionList
                tmp = []
                if idx > 0:
                    tmp.extend(expressionList[:(idx*2)])
                
                tmp.append(calcOperation(expressionList[idx*2], expressionList[idx*2+1], expressionList[idx*2+2]))
                
                if idx < (len(expressionList) - 3) // 2:
                    tmp.extend(expressionList[(idx*2 + 3):])
                    
                selectOperation(tmp)
        
        if len(expressionList) == 1:
        	return expressionList
        selectOperation(expressionList)
        return list(ans)

• 하지만 해당 풀이는 두 가지 문제점을 가지고 있었다.
  • 출력값은 중복된 값을 포함할 수 있다. 따라서 ans는 set으로 표현되면 안된다.
  • ans를 set에서 list로 바꾸게 되면 상단의 알고리즘에서는, 첫 번째 operator 선택 -> 네 번째 operator 선택 과 '네 번째 operator 선택 -> 첫 번째 operator 선택` 을 다른 값으로 인식하게 된다. 다시 말해, operator가 8개 있다면 8! 개의 값을 출력하게 된다는 것이다.
• 해당 접근 방법으로는 올바른 값을 출력할 수 없어, 새로운 알고리즘을 생각했다.
• 선택된 operator의 왼쪽과 오른쪽 expressionList에서 가능한 value들을 list로 각각 받아와, 해당 값들을 계산해 반환 해주는 방식으로 최종적인 알고리즘을 구현했다.

✨ 문제 풀이

from itertools import product

class Solution:
    def diffWaysToCompute(self, expression: str) -> List[int]:
    	# 주어진 expression 문자열을 number와 operator로 parse하는 과정
        expressionList = []
        
        num_st, num_end = 0, 0
        while num_end < len(expression):
            if ord('0') <= ord(expression[num_end]) <= ord('9'):
                num_end += 1
                continue
            
            expressionList.append(int(expression[num_st:num_end]))
            expressionList.append(expression[num_end])
            
            num_st = num_end = num_end + 1
        
        expressionList.append(int(expression[num_st:]))
        
        # 주어진 숫자와 operator를 바탕으로 계산
        def calcOperation(firstNum, operation, secondNum):
            if operation == '+':
                return firstNum + secondNum
            elif operation == '-':
                return firstNum - secondNum
            else:
                return firstNum * secondNum
        
        # expressionList 내의 모든 opereator에 대해,
        # operator 왼쪽의 expressionList와 오른쪽의 expressionList에 대해 계산 가능한 값들을 가져와
        # list에서 하나씩 가져와 모두 계산해준 list를 반환
        def selectOperation(expressionList):
            if len(expressionList) == 1:
                return expressionList
            
            ans = []
            for idx in range((len(expressionList) - 1) // 2):
                operator = expressionList[idx * 2 + 1]
                
                for firstNum, secondNum in product(selectOperation(expressionList[:(idx*2+1)]), selectOperation(expressionList[(idx*2+2):])):
                    ans.append(calcOperation(firstNum, operator, secondNum))
                    
            return ans
        
        return selectOperation(expressionList)

• 처음 돌렸을 때 99%가 나와서 코드를 꽤 잘 짰다 생각했는데, 다시 돌려보니 평균 이하의 빠르기가 나온다. leetCode의 runtime 측정은 굳이 확인하지 않는 것으로.
• 코드 작성 후 discuss 탭에서 여러 사람들의 풀이를 살펴보다 재밌는 풀이를 발견했다. [링크]

class Solution(object):
    def diffWaysToCompute(self, input):
        m = {}
        return self.dfs(input, m)
        
    def dfs(self, input, m):
        if input in m:
            return m[input]
        if input.isdigit():
            m[input] = int(input)
            return [int(input)]
        ret = []
        for i, c in enumerate(input):
            if c in "+-*":
                l = self.diffWaysToCompute(input[:i])
                r = self.diffWaysToCompute(input[i+1:])
                ret.extend(eval(str(x)+c+str(y)) for x in l for y in r)
        m[input] = ret
        return ret

• 중복되게 계산되어 발생하는 redundancy를 막기 위해 memoization을 진행했다고 한다. 모든 알고리즘이 그렇지만, runtime을 줄이기 위해 memory usage를 희생한 셈.
  • 해당 코드에서 left, right을 계산한 방법이 흥미로웠다. 나처럼 parsing을 먼저 진행하지 않더라도 isdigit() 함수를 잘 이용해 보다 가볍게 iteration을 돌 수 있다는 사실을 알게 되었다.