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

링크: 2020 카카오 인턴십 > 수식 최대화

풀이(python)

from itertools import permutations

def solution(expression):
    answer = 0    
    expressionList = list(expression.replace('+', ' + ')
                       .replace('-', ' - ')
                       .replace('*', ' * ')
                       .split(' '))
    
    operation = [ch for ch in expression if not ch.isdigit()] # 연산자만 분리한 리스트
    precedences = list(permutations(set(operation))) # 연산자 우선순위 순열

    for precedence in precedences:
        tmpList = expressionList

        for pre in precedence:
                stack = []
                for num2 in tmpList:
                    if stack and stack[-1] == pre:
                        stack.pop()
                        num1 = stack.pop()
                        stack.append(str(eval(num1 + pre + num2)))
                    else:
                        stack.append(num2)
                tmpList = stack

        answer = max(answer, abs(int(tmpList[0])))

    return answer

설명

• 숫자와 연산자로 이어진 문자열을 리스트의 원소들로 만들었다. 연산자는 숫자 사이에 있기 때문에 연산자 앞뒤로 공백을 만들어주고, 공백을 기준으로 split했다.
• 연산자 우선순위 정의는 순열을 통해 만든다. (permutations 사용) 그리고 중복되는 연산자도 있을 수 있으니 set()을 사용한다.
• 우선순위 순열을 하나씩 계산해서 확인하며 최댓값을 구한다. 계산은 중간 결과값을 저장하기 좋은것 같아 스택을 사용했다.
• 현재 계산해야되는 연산자가 오면 스택에서 pop후 계산해서 push한다.

  예를 들어 우선순위가 * > - > +일때, *부터 계산한다. 스택에 원소를 하나씩 넣다가 스택의 최상단 값이 *이면 두번 꺼내서 계산한 후 결과값을 넣는다.
  이때 처음 꺼내지는건 연산자이고 두번째로 꺼내지는건 숫자num1이다.
  *연산 후 남은 수식들이 tmpList에 들어간다. *연산이 끝난후 다음으로 우선순위가 높은 -와 +를 계산한다.

• 수식내 모든 연산자를 계산하면 tmpList에는 최종 결과값만 남는다. 최종 결과값의 절대값과 answer중 더 큰값을 answer에 넣는다.

쉽지 않았ㄷr..