[programmers/py] 수식 최대화

수식 최대화

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

문제 설명

해커톤 참가자는 +, -, *연산자가 포함된 수식을 전달받아 절대값이 가장 큰 수를 제출해야 합니다.
각 연산자의 우선순위는 참가자가 자유롭게 설정할 수 있지만, 연산자의 우선순위가 같을 수 는 없습니다.

참가자에게 주어진 연산 수식이 담긴 문자열 expression이 매개변수로 주어질 때, 우승 시 받을 수 있는 가장 큰 상금 금액을 return 하도록 solution 함수를 완성해주세요.

풀이 설명

연산자의 조합이 총 6개, expression의 길이가 100이하인 문자열이라 brute-force로 해결 가능합니다

1. 조합을 만들기 위해 permutations를 불러옵니다.
2. 각 조합을 만들고 숫자만 있는 배열 split_list, 각 연산자를 보관하는 op배열을 만들어 줍니다.
3. 우선순위에 따라 결과를 계산해 answer에 저장해 줍니다.
4. 절대값이 큰 값을 반환

from itertools import permutations
from re import split

def solution(expression):
    answer = []
    
    for pri in permutations(["-", "+", "*"], 3):
        # 숫자들, [100, 200, 300, 500, 20]
        split_list = list(map(int, split('[\+\-\*]', expression)))
        
        # 연산자, ["-", "*", "-", "+"]
        op = [c for c in expression if c in "+-*"]
        
        for p in pri:
            while p in op:
                i = op.index(p) # 연산자 위치
                
                if p == "*":
                    val = split_list[i] * split_list[i+1]
                elif p == "-":
                    val = split_list[i] - split_list[i+1]
                else :
                    val = split_list[i] + split_list[i+1]
                
                split_list[i] = val # 연산한 값으로 변경
                split_list.pop(i+1) # 1+2면 2는 pop, 1은 3으로 변경
                
                op.pop(i) # 사용한 연산자 제거
        
        answer.append(split_list[0])
    
    return max(abs(n) for n in answer)

# *-+가 나올 수 있는 경우를 계산
# 경우에 따라 값을 계산 후 큰 값을 리턴?

느낀점

처음에는 각 연산자에 따라 DFS를 써서 문제를 풀고있었는데 expression의 길이나 연산자 조합 수를 보고 brute-force를 통해 해결할 수 있다는 것을 알았다.

좀 더 문제를 보고 시간 복잡도를 생각해 봐야할 것 같다.