[프로그래머스/Python] 수식 최대화 (반복/재귀)

코딩테스트 연습 - 수식 최대화

1. 반복문 풀이

from itertools import permutations

def calc(prior, exp):
    
    for i in prior:
        while i in exp:
            idx = exp.index(i)
            exp[idx-1] = str(eval(exp[idx-1]+exp[idx]+exp[idx+1]))
            exp = exp[:idx] + exp[idx+2:]

    return exp[0]


def solution(expression):
    
    # 1)우선순위 만들기
    operators = list(permutations(['*','+','-'],3))
    
    # 2)숫자와 연산자를 분리시킨 리스트 만들기
    exp = []
    start = 0
    for i, char in enumerate(list(expression)):
        if char in ['*','+','-']:
            exp.append(expression[start:i])
            exp.append(expression[i])
            start = i+1
    exp.append(expression[start:])

    # 3)우선순위를 돌면서 값 뽑아내기
    answer = 0
    for prior in operators:
        answer = max(answer,abs(int(calc(prior, exp[:]))))
                      
    return answer

 

2. 재귀풀이

from itertools import permutations

def calc(p, n, expression):
    """
    p: 지금 우선순위들
    n: depth
    expression: 수식
    """
    
    if n == 2: #base case
        return str(eval(expression))
    
    if p[n] == '*':
        res = eval('*'.join([calc(p, n+1, i) for i in expression.split('*')]))
        return str(res)
    if p[n] == '+':
        res = eval('+'.join([calc(p, n+1, i) for i in expression.split('+')]))
        return str(res)
    if p[n] == '-':
        res = eval('-'.join([calc(p, n+1, i) for i in expression.split('-')]))
        return str(res)

def solution(expression):
    
    prior = list(permutations(['*','+','-'],3))
    
    #우선순위를 돌면서 마지막에 숫자값을 return받으면서 계속 최댓값 업데이트
    answer = 0
    for p in prior:
        answer = max(answer, abs(int(calc(p, 0, expression))))    
    return answer