[프로그래머스] 수식 최대화 (파이썬)

문제 출처: 프로그래머스

프로그래머스

 

문제 설명

출처: 프로그래머스

---

출처: 프로그래머스

처음 열었을 때 아 그냥 문자열 파싱 문제인가 생각했지만 생각보다 까다로운 구현과정이 내포된 문제였다.

 

정말 다행스럽게도 연산자가 3개 밖에 없고, 문자열의 길이도 100이 제한이었기 때문에 시간 복잡도를 고려하지 않고 문제를 풀어나갔다.

 

<정답 코드>

from itertools import permutations
from collections import deque


def ex_split(ex):
    reg = []
    tmp = ''
    for i in ex:
        if i.isdigit():
            tmp += i
        else:
            reg.append(int(tmp))
            reg.append(i)
            tmp = ''

    if tmp:
        reg.append(int(tmp))
    return reg


def solution(expression):
    answer = 0
    expression = ex_split(expression)

    for case in permutations(['+', '-', '*'], 3):
        temp = deque(expression)
        for operator in case:
            ans = deque()
            while len(temp):
                cur = temp.popleft()

                if cur == operator:
                    a = ans.pop()
                    b = temp.popleft()
                    ans.append(eval(str(a)+cur+str(b)))
                else:
                    ans.append(cur)

            temp = ans

        answer = max(abs(temp[0]), answer)

    return answer

피연산자와 연산자를 구분하고 연산 자체도 구현해야하는 번거로운 문제였기에 코드도 조금 길어졌다.

 

접근은 아래와 같다.

1. 인자로 받은 expression 식을 숫자와 연산자로 구분한다.
2. permutation을 이용해 연산자의 계산 순서를 정의한다.
3. 하나의 연산자 순서를 순회하면서 해당 연산자가 존재하는 양옆을 연산하며 전체를 순회한다.
4. 최대값을 갱신한다.

eval을 통해서 문자열 수식을 간단하게 계산할 수 있는 점이 좋았다.

 

다른 사람들을 보니, 문자열 포맷팅을 통해 간단히 구현한 사람도 있고 regex를 활용해 간단히 푼 사람도 있었다. 코드를 참조해서 발전해보도록 하자..