[파이썬] 수식 최대화 - 2020 카카오 인턴십 [CODING TEST #18]

https://school.programmers.co.kr/learn/courses/30/lessons/67257

 

 

정말 까다로운 문제였다... 두 자리 이상의 operand를 따로 저장하는 아이디어랑, 슬라이싱으로 temp_list를 갱신하는 아이디어도 잘 떠오르지 않아서 시간이 오래 걸렸다.

 

from itertools import permutations
def solution(expression):
    operators = ["*", "+", "-"]
    answer = []
    # 모든 연산 우선순위 조합에 대해 반복
    for operator in permutations(operators, 3):
        temp_exp = [""]
        for exp in expression: # operand : 문자열이므로 기존 숫자에 이어붙이기
            if exp.isdigit() and temp_exp[-1] not in operators:
                temp_exp[-1] += exp
            else: # operator OR operand 첫 글자 : 따로 append 
                temp_exp.append(exp)
        for i in operator:
            while i in temp_exp:
                idx = temp_exp.index(i)
                # idx - 1 , idx , idx + 1은 eval() 함수로 계산한 값을 저장,
                # 슬라이싱으로 temp_exp 갱신
                temp_exp = temp_exp[:idx-1]+[str(eval("".join(temp_exp[idx-1:idx+2])))]+temp_exp[idx+2:]
        answer.append(abs(int(temp_exp[0])))
    return max(answer)

 

다른 좋은 풀이를 찾아봤는데, 재귀 함수를 만들어서 우선순위가 낮은 operator로 split한 리스트를 계속 호출하여 priority[2]일 경우 해당 표현식을 eval() 함수로 계산하여 반환하고, join()으로 결과값을 다시 연산 기호로 합치고 eval() 함수로 계산하도록 구현한 코드가 있었다. 분할-정복 아이디어를 이렇게 사용할 수 있다니 놀라웠다....

실전에서 써먹을 수 있을 진 모르겠지만 정말 좋은 아이디어다.

 

from itertools import permutations
def calc(priority, n, expression):
    if n == 2:
        return str(eval(expression))
    if priority[n] == '*':
        res = eval('*'.join([calc(priority, n + 1, e) for e in expression.split('*')]))
    if priority[n] == '+':
        res = eval('+'.join([calc(priority, n + 1, e) for e in expression.split('+')]))
    if priority[n] == '-':
        res = eval('-'.join([calc(priority, n + 1, e) for e in expression.split('-')]))
    return str(res)


def solution(expression):
    answer = 0
    priorities = (list(permutations(['*','-','+'], 3)))
    for priority in priorities:
        res = int(calc(priority, 0, expression))
        answer = max(answer, abs(res))

    return answer