📗 수식 최대화

프로그래머스

from itertools import permutations

def solution(expression):
    answer = 0
    operators = ['+', '-', '*']
    
    nums, ops = [], []
    num = ''
    
    for char in expression:
        if char.isdigit():
            num += char
        else:
            nums.append(int(num))
            num = ""
            ops.append(char)
    nums.append(int(num))
    
    for op_order in permutations(operators):
        temp_nums = nums[:]
        temp_ops = ops[:]
        
        for op in op_order:
            idx = 0
            while idx < len(temp_ops):
                if temp_ops[idx] == op:
                    if op == '+':
                        temp_nums[idx] += temp_nums[idx+1]
                    elif op == '-':
                        temp_nums[idx] -= temp_nums[idx+1]
                    else:
                        temp_nums[idx] *= temp_nums[idx+1]
                    temp_nums.pop(idx+1)
                    temp_ops.pop(idx)
                else:
                    idx += 1
                    
        answer = max(answer, abs(temp_nums[0]))
        
    return answer

• 우선순위 조합을 활용하여 수식의 최댓값을 반환해주는 문제였습니다.

왜 이렇게 풀었을까?

• 처음에 접근할 때에는 stack을 이용하여 풀까 하다가 숫자와 연산자의 구분이 필요한 시점에서 stack이 그다지 효율적으로 동작하지 않게 되어, 먼저 수식에서 숫자와 연산자를 각각 리스트에 담아준 뒤 시작을 해보았습니다.
• 조합이 그리 많지 않아 일일이 조합을 명시한 뒤 풀어도 되었겠지만, 코드의 간결성을 위해 permutations를 사용하여 조합을 계산했습니다.
• temp_ops는 연산이 진행되면 그 길이가 동적으로 변하기 때문에 이를 처리하기 위해 while문의 조건을 idx < len(temp_ops)로 설정함으로써 그 길이에 맞추어 연산이 진행되게끔 했습니다.
• 시간 초과가 날까 싶어 계속 반신반의하며 코드를 작성하였는데 통과를 하게 되어 다행이고, 추후에 더 효율적인 방법을 탐구해볼 예정입니다.