[알고리즘] 프로그래머스 Lv2 수식최대화

문제

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

풀이과정

수식 문제라서 보자마자 후위표기식으로 변환해야겠다는 생각을 했다.
그러나, 변환방법을 까먹은 것이다...
원리를 생각하며 코드를 생각해내보려했지만, 실패해서 결국 검색해서 공부를 했다.

후위표기식 변환방법은 아래의 블로그를 참고했다.
https://woongsios.tistory.com/288

중위표기식으로 쓰인 수식을 후위표기식으로 변환하는 과정(괄호가 없는 경우)
0. 연산자를 담는 stack을 만든다
1. 숫자를 만나면 push
2. 연산자를 만나면,
2-1. 연산자 stack이 비었다면, stack에 연산자 push
2-2. 연산자 stack에 연산자가 있다면, 현재 연산자와 stack의 마지막에 위치한 연산자의 우선순위를 비교하고, 현재 연산자의 순위가 낮을 때까지 연산자를 stack에서 pop해서 후위표기식에 push 한다(=> 현재 연산자의 순위가 stack[-1]보다 높거나 같으면 stack.pop(), 낮으면 그때 현재 연산자를 stack에 push)
3. 주어진 중위표기식을 모두 살펴보았으면, stack에 남은 연산자를 끝에서부터(stack개념으로 LIFO) 빼서 후위표기식에 추가한다

해당 문제는, 문자열로 주어진 expression에서 숫자와 연산자를 잘 분리할 수 있는지 + 중위표기식을 후위표기식으로 변환하여 계산할 수 있는지 가 중요했다고 생각된다.

수식의 우선순위로 가능한 모든 경우를 미리 리스트화한 후, 이를 순회하면서 후위표기식으로 바꾸고 계산한 결과에 절댓값을 씌워 answer에 추가한 다음 answer의 최댓값을 구했다.

코드

from collections import deque

# 수식의 우선순위가 가능한 모든 경우를 미리 리스트화한 후 순회하면서, 중위표기식을 후위표기식으로 바꾸어 계산한 결과의 절댓값의 최댓값을 구함
def solution(expression):
    op_orders = [['-','*','+'], ['-','+','*'], ['*','-','+'], ['*','+','-'], ['+','*','-'], ['+','-','*']]
    answer = []

    for order in op_orders:
        start = 0
        postfix = deque()
        operators = deque() # stack

        for i in range(len(expression)):
            if not expression[i].isdigit():
                postfix.append(int(expression[start:i]))
                start = i+1
                while operators:
                    op1 = operators[-1]
                    op2 = expression[i]
                    if order.index(op1) <= order.index(op2):
                        postfix.append(operators.pop())
                    else:
                        operators.append(op2)
                        break
                else:
                    operators.append(expression[i])

        postfix.append(int(expression[start:]))
        while operators:
            postfix.append(operators.pop())

        stack = []
        idx = 0
        while idx < len(postfix):
            if type(postfix[idx]) != int:
                a = stack.pop()
                b = stack.pop()
                if postfix[idx] == '+':
                    stack.append(a+b)
                elif postfix[idx] == '-':
                    stack.append(b-a)
                elif postfix[idx] == '*':
                    stack.append(a*b)

            else:
                stack.append(postfix[idx])
            idx += 1

        # print(order)
        # print(postfix)
        # print(stack)
        answer.append(abs(stack[-1]))

    return max(answer)



ep = "100-200*300-500+20"
ep = "50*6-3*2"

print(solution(ep))

• 처음에 deque를 안쓰고 list로만 구현했을 때, 테스트케이스 별 실행 시간
  
• deque를 적용한 후, 테스트케이스 별 실행 시간
  

이 정도 범위에서는 큰 차이가 없는 듯 하다.

다른 사람의 풀이

eval이라는 내장 함수를 사용한 풀이

def solution(expression):
    operations = [('+', '-', '*'),('+', '*', '-'),('-', '+', '*'),('-', '*', '+'),('*', '+', '-'),('*', '-', '+')]
    answer = []
    for op in operations:
        a = op[0]
        b = op[1]
        temp_list = []
        for e in expression.split(a):
            temp = [f"({i})" for i in e.split(b)]
            temp_list.append(f'({b.join(temp)})')
        answer.append(abs(eval(a.join(temp_list))))
    return max(answer)