문제유형
- 분할정복
분할정복
- 큰 문제를 작은 문제로 쪼갤 수 있다
- 큰 문제와 작은 문제 풀이법이 같다
- 큰 문제의 답은 작은 문제의 답을 사용해 구할 수 있다
- 문제 풀이가 큰 문제, 작은 문제 모두 동일하므로 당연히 재귀를 사용해 구현한다
문제설명
- 연산자 우선순위를 바꿔가며 값이 최대가 되는 경우를 찾아라
풀지 못했던 이유
- 스트링에서 각 연산자를 찾아 결과를 계산하고 스트링을 다시 만들어주면 된다고 생각했음
- 스트링의 인덱스 처리를 제대로 못해서 못풀었음
- 문제 유형은 정해져 있으므로, 분할정복, 그래프 탐색, DP 등 정해진 유형의 문제인지 먼저 고민해봤어야 함
풀이설명
- 우선순위가 높은 연산자 기준으로 문제를 나누고
- 더이상 나눌 수 없을 때까지 나눈 후 (마지막 연산자)
- 작은 문제의 계산결과를 사용해 큰 문제의 계산 결과를 리턴
def calc(priority, n, expression):
if n == 2:
return str(eval(expression))
res = None
if priority[n] == '*':
res = eval('*'.join([calc(priority, n+1, e) for e in expression.split('*')]))
elif priority[n] == '-':
res = eval('-'.join([calc(priority, n+1, e) for e in expression.split('-')]))
elif priority[n] == '+':
res = eval('+'.join([calc(priority, n+1, e) for e in expression.split('+')]))
return str(res)
def solution(expression):
order = [('*','-','+'),
('*','+','-'),
('+','*','-'),
('+','-','*'),
('-','*','+'),
('-','+','*')]
out = 0
for priority in order:
out = max(out, abs(calc(priority, 0, expression)))
return out
