파이썬 알고리즘 인터뷰84번(리트코드 241번) Different Ways to Add Parentheses
https://leetcode.com/problems/different-ways-to-add-parentheses/
스스로 풀지 못했다.
책 풀이를 보고 이해한 후 보지 않고 스스로 코드를 작성했다.
그런데 속도가 빠른 편이 아니라 다른 사람들의 풀이를 찾아보았다.
저마다 조금씩 다른 방법으로 최적화를 하였다.
다른 풀이1(Recursion)
class Solution:
def diffWaysToCompute(self, expression: str) -> List[int]:
if expression.isnumeric():
return [int(expression)]
def operation(left, right, operator):
output = []
for l in left:
for r in right:
output.append(eval(str(l) + operator + str(r)))
return output
result = []
for i, char in enumerate(expression):
if char in '+-*':
left = self.diffWaysToCompute(expression[:i])
right = self.diffWaysToCompute(expression[i + 1:])
result.extend(operation(left, right, char))
return result- 책 풀이
- 처음에 잘 이해하기 어려웠는데 아래 예시를 보면 이해가 쉽다.
iteration 1:
2 - 1- 1 + 1
/ \
2 - (1-1+1)
/ / \
2 - (1 - (1+1))
then
2 - 1- 1 + 1
/ \
2 - (1-1+1)
/ / \
2 - ((1 -1)+1)
This give us
1. 2-(1 - (1+1))=3
2. 2 -(1 -1)+1))=1
iteration 2:
2 - 1 - 1 + 1
/ \
(2 -1)-(1 + 1)
this give us
1. (2-1)-(1+1) = -1
iteration 3:
2 - 1- 1 + 1
/ \
(2 - 1 - 1) + 1
/ \ \
(2 - (1 - 1)) + 1
then
2 - 1- 1 + 1
/ \
(2 - 1 - 1) + 1
/ \ \
((2 - 1) - 1) + 1
this give us
1. 2 - (1 - 1)) + 1=3
2. ((2 - 1) - 1) + 1=1
So the solution is [3,1,-1,3,1]다른 풀이2(Recursion)
class Solution:
def diffWaysToCompute(self, expression: str) -> List[int]:
res = []
for i in range(len(expression)):
oper = expression[i]
if oper == "+" or oper == "-" or oper == "*":
sub_str1 = expression[0 : i]
sub_str2 = expression[i + 1 : ]
s1 = self.diffWaysToCompute(sub_str1)
s2 = self.diffWaysToCompute(sub_str2)
for i in s1:
for j in s2:
if oper == "*":
res.append(int(i) * int(j))
elif oper == "+":
res.append(int(i) + int(j))
else:
res.append(int(i) - int(j))
if len(res) == 0:
res.append(int(expression))
return res- 다른 풀이1에서
eval은 문자열을 변환하고 실행하는 과정이 필요하여 느림. - 직접 연산하는 것으로 바꾸면 더 빠르다.
- 다른 풀이1의
expression.isnumeric()과 다른 풀이2의len(res) == 0은 모두 연산 없는 수의 경우를 검사한다.
다른 풀이3(Recursion)
class Solution:
def diffWaysToCompute(self, expression: str) -> List[int]:
@cache
def dfs(exp):
if exp.isdigit():
return [int(exp)]
ans = []
for i, c in enumerate(exp):
if c in '-+*':
left, right = dfs(exp[:i]), dfs(exp[i + 1 :])
for a in left:
for b in right:
if c == '-':
ans.append(a - b)
elif c == '+':
ans.append(a + b)
else:
ans.append(a * b)
return ans
return dfs(expression)1-2-3-4를 예시로 보면1-2를 여러 번 계산하게 된다.- 이를 저장해두고 사용하면 빨라진다.
- 직접 딕셔너리 등을 이용하여 기록해도 된다. (다른풀이 5)
- 하지만 더 편한 방법이 있다.
@cache를 사용하면 한 번 계산한 결과를 저장해 두고, 같은 입력이 다시 들어오면 계산하지 않고 저장된 값을 반환함.
다른 풀이4(Recursion)
class Solution:
def isOperator(self, ch):
return ch == '+' or ch == '-' or ch == '*'
def getDiffWays(self, i, j, expression):
res = []
if j - i + 1 <= 2:
res.append(int(expression[i:j + 1]))
return res
for ind in range(i, j + 1):
if self.isOperator(expression[ind]):
op = expression[ind]
left = self.getDiffWays(i, ind - 1, expression)
right = self.getDiffWays(ind + 1, j, expression)
for l in left:
for r in right:
if op == '+':
res.append(l + r)
elif op == '-':
res.append(l - r)
elif op == '*':
res.append(l * r)
return res
def diffWaysToCompute(self, expression: str):
n = len(expression)
return self.getDiffWays(0, n - 1, expression)- 위 풀이와 논리는 같음.
- 다만 문자열
expression[i:j]을 새로 생성하는 것을 최대한 줄이고, 인덱스로만 접근하여 조금 더 빠르다.
다른 풀이5(DP - Memoization)
class Solution:
def isOperator(self, ch):
return ch == '+' or ch == '-' or ch == '*'
def getDiffWays(self, i, j, dp, expression):
if (i, j) in dp:
return dp[(i, j)]
len_substring = j - i + 1
if len_substring <= 2:
result = [int(expression[i:j+1])]
dp[(i, j)] = result
return result
res = []
for ind in range(i, j + 1):
if self.isOperator(expression[ind]):
op = expression[ind]
left = self.getDiffWays(i, ind - 1, dp, expression)
right = self.getDiffWays(ind + 1, j, dp, expression)
for l in left:
for r in right:
if op == '+':
res.append(l + r)
elif op == '-':
res.append(l - r)
elif op == '*':
res.append(l * r)
dp[(i, j)] = res
return res
def diffWaysToCompute(self, expression: str):
dp = {}
return self.getDiffWays(0, len(expression) - 1, dp, expression)- 한 번 계산한 값을
dp에 기록, 이용하여 연산을 줄여 빠르다.
다른 풀이6(DP - Tabulation)
class Solution:
def isOperator(self, ch):
return ch == '+' or ch == '-' or ch == '*'
def diffWaysToCompute(self, expression: str) -> List[int]:
n = len(expression)
dp = [[[] for _ in range(n)] for _ in range(n)]
def isValidExpression(i, j):
return (i == 0 or self.isOperator(expression[i - 1])) and (j == n - 1 or self.isOperator(expression[j + 1]))
for i in range(n):
if isValidExpression(i, i):
dp[i][i] = [int(expression[i])]
for i in range(n - 1):
if isValidExpression(i, i + 1):
dp[i][i + 1] = [int(expression[i:i + 2])]
for length in range(3, n + 1):
for i in range(n - length + 1):
j = i + length - 1
if not isValidExpression(i, j):
continue
dp[i][j] = []
for ind in range(i, j + 1):
if self.isOperator(expression[ind]):
op = expression[ind]
left = dp[i][ind - 1]
right = dp[ind + 1][j]
for l in left:
for r in right:
if op == '+':
dp[i][j].append(l + r)
elif op == '-':
dp[i][j].append(l - r)
elif op == '*':
dp[i][j].append(l * r)
return dp[0][n - 1]배운 점
eval@cacheDynamic Programming의 종류:Tabulation과Memoization
개발 공부하는 30대 비전공자 직장인