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

📌 프로그래머스 [수식 최대화]

🔗 문제 링크

---

문제 설명 📄

주어진 수식에서 연산자의 우선순위를 조정하여 최댓값을 구하는 문제.
가능한 연산자는 +, -, *이며, 이들의 우선순위를 자유롭게 설정할 수 있음.
연산자의 우선순위에 따라 계산을 수행한 후, 최댓값을 반환해야 함.

---

문제 접근 방식 💡

• 토큰화: 정규 표현식을 활용하여 숫자와 연산자를 분리.
• 우선순위 조합 생성: permutations을 이용하여 연산자 우선순위 경우의 수 생성.
• 계산 수행:
  • 현재 우선순위에 따라 반복적으로 연산을 수행.
  • deque를 활용하여 좌에서 우로 연산을 적용하며 피연산자를 갱신.
• 최댓값 갱신: 모든 경우의 수를 수행한 후, 절댓값이 가장 큰 결과 반환.

---

Solution 💻

import re
from itertools import permutations
from collections import deque

def solution(expression):
    tokens = re.findall(r'\d+|[+\-*]', expression)
    
    operators = {t for t in tokens if t in ['-', '+', '*']}
    operator_perms = list(permutations(operators))
    
    def calc(a, b, op):
        a, b = int(a), int(b)
        if op == '+':
            return a + b
        elif op == '-':
            return a - b
        else:  # '*'
            return a * b

    result = 0
    
    for priority in operator_perms:
        exp = deque(tokens)
        
        for op in priority:
            temp = deque()
            while exp:
                x = exp.popleft()
                if x == op:
                    left_operand = temp.pop()
                    right_operand = exp.popleft()
                    temp.append(calc(left_operand, right_operand, x))
                else:
                    temp.append(x)
            exp = temp
        
        result = max(result, abs(int(exp[0])))
    
    return result

시간 복잡도 분석 ⏲️

• 시간 복잡도: O(3! × n) = O(6n)
  • 연산자의 순열이 최대 3! = 6가지.
  • 각 경우에 대해 O(n) 연산을 수행하므로 최악의 경우 O(6n).
  • n은 수식의 길이.

공간 복잡도 분석 🗄️

• 공간 복잡도: O(n)
  • tokens, deque, operator_perms 등의 저장 공간 사용.

---

리팩토링 🛠️

import re
from itertools import permutations

def solution(expression):
    tokens = re.findall(r'\d+|[+\-*]', expression)
    operator_perms = permutations(set(tokens) & {'+', '-', '*'})

    def evaluate(exp, op_order):
        for op in op_order:
            stack = []
            while exp:
                token = exp.pop(0)
                if token == op:
                    stack.append(str(eval(stack.pop() + op + exp.pop(0))))
                else:
                    stack.append(token)
            exp = stack
        return abs(int(exp[0]))

    return max(evaluate(tokens[:], order) for order in operator_perms)

시간 복잡도 분석 ⏲️

• 시간 복잡도: O(6n)
  • 연산자 순열 6개에 대해 O(n) 연산 수행.

공간 복잡도 분석 🗄️

• 공간 복잡도: O(n)
  • 리스트 stack과 exp 사용.

---

✅ 리팩토링된 코드의 개선점

• deque 대신 리스트(list.pop(0)) 사용하여 가독성 향상.
• eval을 활용하여 연산 간소화.
• 리스트 슬라이싱(tokens[:])을 이용하여 원본 유지.