[프로그래머스] 수식 최대화(Python)

문제

수식 최대화

문제 해설

수식의 우선순위를 모두 구하고 식에 대입하여 나올 수 있는 최대 값을 구하는 문제이다. 우선순위가 나오는 경우는 최대 3! 이므로 리스트에 따로 저장해 두었다. 만일 수기로 작성하기 힘든 경우의 수가 나올 것 같으면 dfs, 순열, 조합등을 이용하여 구현하면 될 것이다.

1. 주어진 expression을 연산자와 피연산자로 구분한 뒤, 각 리스트에 저장한다.
2. 저장해놓은 연산자별 우선순위를 이용해 계산한다.

소스 코드

def calculate(seq, operator, operand):
    calculate_seq = [
        ["*", "+", "-"],
        ["*", "-", "+"],
        ["+", "*", "-"],
        ["+", "-", "*"],
        ["-", "*", "+"],
        ["-", "+", "*"],
    ]
    cal_operator = operator[:]
    cal_operand = operand[:]
    for i in range(3):
        idx = 0
        while idx < len(cal_operator):
            if calculate_seq[seq][i] == cal_operator[idx]:
                a = int(cal_operand.pop(idx))
                b = int(cal_operand.pop(idx))
                op = str(cal_operator.pop(idx))
                # 계산
                if op == "*":
                    cal_operand.insert(idx, a * b)
                elif op == "+":
                    cal_operand.insert(idx, a + b)
                else:
                    cal_operand.insert(idx, a - b)
                idx -= 1
            idx += 1
    # 마지막 남은 피연산자 절대값 씌워 리턴
    return abs(cal_operand[0])

def solution(expression):
    answer = 0
    operator = []
    
    for i in range(len(expression)):
        if expression[i] == "-" or expression[i] == "*" or expression[i] == "+":
            operator.append(expression[i])
    expression = expression.replace("*", ",")
    expression = expression.replace("+", ",")
    expression = expression.replace("-", ",")
    operand = list(map(int, expression.split(",")))
    for i in range(6):
        answer = max(calculate(i, operator, operand), answer)
    return answer