[프로그래머스] 수식 최대화 (파이썬 풀이)

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

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

내 풀이:

from itertools import permutations

# 수식을 해당 연산자에 대해 연산한 후의 수식 리턴
def calculate(operator, expression):
    new_exp = []
    i = 0
    while i < len(expression):
        if expression[i] == operator:
            new_exp.append(str(eval(new_exp.pop() + expression[i] + expression[i + 1])))
            i += 2
        else:
            new_exp.append(expression[i])
            i += 1

    return new_exp

def solution(expression):
	# 수식을 연산자 기준으로 나누고, 연산자들 저장
    stack, operator = [] * 100, []      
    for char in expression:
        if char.isdigit():
            if stack and stack[-1].isdigit():
                stack[-1] += char
            else:
                stack.append(char)
        else:
            stack.append(char)
            if char in operator:
                continue
            operator.append(char)

	# 연산자 우선순위의 모든 조합에 대한 최종 계산값 갱신하며 최댓값 추출
    result = 0
    for rank in permutations(operator, len(operator)):
        exp = stack[:]
        for r in rank:
            stack = calculate(r, stack)
        result = max(result, abs(int(stack[0])))
        stack = exp

    return result

• 아이디어:모든 우선순위 조합에 대해 완전탐색으로 계산 후 그중 최댓값을 정답으로 반환
• 아이디어보다는 우선순위에 맞게 연산하는 과정을 구현하는데 매우 오랜 시간이 걸렸음
  • for문으로 수식 돌면서 필요시 계산 후 빈 리스트에 차곡차곡 append 했으면 되는 것을 수식 자체를 바꾸면서 반복문을 돌다보니 오래 걸림 (실수)
  • eval() -> int 라서 str으로 다시 변환 필요

참고 풀이:

from itertools import permutations

def solution(expression):
    answer = []
    for op in permutations(('+', '-', '*'), 3):
        third, second = op[0], op[1]
        temp_list = []
        # 역순으로 올라가면서 괄호 처리
        for e in expression.split(third):
            temp = [f'({i})' for i in e.split(second)]
            temp_list.append(f'({second.join(temp)})')
        answer.append(abs(eval(third.join(temp_list))))
        
    return max(answer)

• 역발상으로 풀이한 기발한 아이디어, 연산자 갯수가 무엇이든 해당하는 풀이
• 괄호 처리를 하는 접근으로 풀이했고, 최종적으로 한번 eval()하면 결과가 나오게끔 되어 매우 깔끔함