[PG/Python] 수식 최대화

📌 문제

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

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

 

📌 문제 접근 방법

1. 후위표기법으로 스택을 사용해서 계산해야겠다는 생각은 금방 했지만,
   우선순위를 표시하는 방법과 후위표기법으로 변환하는 과정을 구현하는데 고민을 오래 했다.
2. 우선순위는 permutations를 사용해서 순열 리스트로 만들어줬다. (인덱스를 활용해서 우선순위를 비교할 것이다)
3. 다음으로 expression 문자열을 순회하면서
   
   1. 숫자라면 num에다 저장
   2. 숫자가 아니라면 지금까지 num에 저장된 값을 stack에 push하고
      1. stack이 비었다면 연산자를 stack에 push
      2. 비어있지 않다면 stack의 top과 연산자의 우선순위를 비교한다.
         1. 연산자의 우선순위가 더 높다면 stack에 push
         2. 아니라면 스택이 비거나, 우선순위가 더 높은 연산자를 만날 때 까지 stack에서 pop해준 뒤, 연산자를 push
   3. 반복문이 끝난 뒤 num에 남아있는 값을 postfix에 마저 저장해준다.
   4. stack에 남아있는 연산자도 모두 pop해서 postfix에 저장해준다.
4. 3번의 과정을 통해 후위표기법으로 변환했다면, 이제 이를 이용해서 계산을 해야한다.
   postfix를 순회하면서
   1. 숫자를 만나면 stack에 push
   2. 아니라면 연산에 필요한 만큼 stack에서 숫자를 pop하여 연산을 수행한다.
5. 모든 계산이 끝난 뒤, stack에 남아있는 값(최종 계산 결과)의 절댓값과 answer의 값을 비교해서 갱신해준다.

 

📌 코드

from itertools import permutations

def calculate(num2, num1, operator):
    if operator == '*':
        return num1*num2
    elif operator == '+':
        return num1+num2
    else:
        return num1-num2
    
    
def solution(expression):    
    answer = 0
    
    temp = ['*', '+', '-']
    # 우선 순위 정하기
    for operator in permutations(temp):
        # 우선 순위에 따라 후위 표기법으로 변경
        postfix = []
        stack = []
        num = ''
        for s in expression:
            if s.isnumeric():
                num += s
            else:
                postfix.append(int(num))
                num = ''
                
                if stack:
                    # 스택의 top보다 우선순위가 높으면 push
                    if operator.index(stack[-1]) > operator.index(s):
                        stack.append(s)
                    # 아닐경우 pop후 push
                    else:
                        while stack and operator.index(stack[-1]) <= operator.index(s):
                            postfix.append(stack.pop())
                        stack.append(s)
                # 스택이 비어있다면 연산자를 push
                else:
                    stack.append(s)

        postfix.append(int(num))

        # 스택에 남아있는 것 모두 pop
        while stack:
            postfix.append(stack.pop())
        
        # 후위표기법 계산
        stack = []
        for x in postfix:
            if type(x) == int:
                stack.append(x)
            else:
                stack.append(calculate(stack.pop(), stack.pop(), x))
        
        answer = max(answer, abs(stack[0]))
                    
    return answer