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

프로그래머스 lv2 - 수식 최대화

# 조건

• 해커톤 대회에 참가하는 모든 참가자들에게는 숫자들과 3가지의 연산문자(+, -, *) 만으로 이루어진 연산 수식이 전달되며, 참가자의 미션은 전달받은 수식에 포함된 연산자의 우선순위를 자유롭게 재정의하여 만들 수 있는 가장 큰 숫자를 제출하는 것입니다.
  • 단, 연산자의 우선순위를 새로 정의할 때, 같은 순위의 연산자는 없어야 합니다. 즉, + > - > * 또는 - > * > + 등과 같이 연산자 우선순위를 정의할 수 있으나 +,* > - 또는 * > +,-처럼 2개 이상의 연산자가 동일한 순위를 가지도록 연산자 우선순위를 정의할 수는 없습니다.
  • 수식에 포함된 연산자가 2개라면 정의할 수 있는 연산자 우선순위 조합은 2! = 2가지이며, 연산자가 3개라면 3! = 6가지 조합이 가능합니다.
• 만약 계산된 결과가 음수라면 해당 숫자의 절댓값으로 변환하여 제출하며 제출한 숫자가 가장 큰 참가자를 우승자로 선정하며, 우승자가 제출한 숫자를 우승상금으로 지급하게 됩니다.
• 예를 들어, 참가자 중 네오가 아래와 같은 수식을 전달받았다고 가정합니다.
  • "100-200*300-500+20"
  • 일반적으로 수학 및 전산학에서 약속된 연산자 우선순위에 따르면 더하기와 빼기는 서로 동등하며 곱하기는 더하기, 빼기에 비해 우선순위가 높아 * > +,- 로 우선순위가 정의되어 있습니다.
• 대회 규칙에 따라 + > - > * 또는 - > * > + 등과 같이 연산자 우선순위를 정의할 수 있으나 +,* > - 또는 * > +,- 처럼 2개 이상의 연산자가 동일한 순위를 가지도록 연산자 우선순위를 정의할 수는 없습니다.
• 수식에 연산자가 3개 주어졌으므로 가능한 연산자 우선순위 조합은 3! = 6가지이며, 그 중 + > - > * 로 연산자 우선순위를 정한다면 결괏값은 22,000원이 됩니다.
• 반면에 * > + > - 로 연산자 우선순위를 정한다면 수식의 결괏값은 -60,420 이지만, 규칙에 따라 우승 시 상금은 절댓값인 60,420원이 됩니다.

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

제한사항

• expression은 길이가 3 이상 100 이하인 문자열입니다.
• expression은 공백문자, 괄호문자 없이 오로지 숫자와 3가지의 연산자(+, -, *) 만으로 이루어진 올바른 중위표기법(연산의 두 대상 사이에 연산기호를 사용하는 방식)으로 표현된 연산식입니다. 잘못된 연산식은 입력으로 주어지지 않습니다.
  • 즉, "402+-561*"처럼 잘못된 수식은 올바른 중위표기법이 아니므로 주어지지 않습니다.
• expression의 피연산자(operand)는 0 이상 999 이하의 숫자입니다.
  • 즉, "100-2145*458+12"처럼 999를 초과하는 피연산자가 포함된 수식은 입력으로 주어지지 않습니다.
  • "-56+100"처럼 피연산자가 음수인 수식도 입력으로 주어지지 않습니다.
• expression은 적어도 1개 이상의 연산자를 포함하고 있습니다.
• 연산자 우선순위를 어떻게 적용하더라도, expression의 중간 계산값과 최종 결괏값은 절댓값이 263 - 1 이하가 되도록 입력이 주어집니다.
• 같은 연산자끼리는 앞에 있는 것의 우선순위가 더 높습니다.

# 접근 방법

• 연산자와 숫자를 나눠서 저장해준다.
  • 연산자의 idx가 0이라면 숫자 리스트의 0번과 1번 인덱스를 연산자 0번 인덱스로 연산해주면 된다.
  • 이 때, 계산한 결과를 nums[idx]에 저장 해준 후 idx+1 번째 값을 pop 해준다.
  • 여기서, 연산자의 idx를 pop 해주지 않아서 시간을 많이 뺏겼다.
  • 또한, 연산자의 idx를 pop 해준 후 인덱스 에러를 해결하기 위하여 while문을 활용해주었다.
• val_op를 pop 해준다면 idx를 그대로, 하지 않는다면 +1 씩 해서 찾아준다.

from copy import deepcopy
def solution(expression):
    # (+,-, *) -> 우선순위를 자유롭게 재정의 가능
    # 동일한 연산자 우선순위는 불가능
    # 계산 결과가 음수라면 해당 숫자의 절댓값으로 변환
    answer = 0
    oper = []
    nums = []
    num = ''

    # 숫자 연산자 나눠서 저장 해주기
    for i in expression:
        if i == '+' or i == '-' or i == '*':
            oper.append(i)
            nums.append(num)
            num = ''
        else:
            num += i
    nums.append(num)

    # 연산자 우선 순위
    prior = [['*', '+', '-'],['*', '-', '+'],['+', '*', '-'],['+', '-', '*'],['-', '*', '+'],['-', '+', '*']]

    result = 0
    for op in prior:
        val_op = deepcopy(oper)
        val_num = deepcopy(nums)
        now_val = ''
        val = 0
        for p in op:
            idx = 0
            while idx < len(val_op):
                if not val_op:
                    break
                if val_op[idx] == p:
                    now_val = eval(str(val_num[idx]) + p + str(val_num[idx+1]))
                    val_num[idx] = now_val
                    val_num.pop(idx+1)
                    val_op.pop(idx)

                    if len(val_num) == 1:
                        print(val_num[0])
                        if abs(val_num[0]) > result:
                            result = abs(val_num[0])
                            break

                    continue
                idx += 1


    answer = result
    return answer

다른 분 풀이

• 문자열 포맷팅을 이용하여 풀었다.
• op에 있는 연산자의 역순으로 계산을 해주며 join과 eval을 사용해주었다.
• split을 이용하여 연산자를 기준으로 2번 나눠주는데, 이렇게 되면
  • 현재 연산자가 + 인 경우, +를 포함한 연산들만 남는다 => [100, 10+20, 50]
  • 역순으로 b와 a로 나눠놨던 연산자를 join을 이용하여 다시 문자열로 만들어 준다. => (100-(10+20)-50) * (30) 과 같이 된다.
  • eval로 연산해준 후 max로 비교

역순과 문자열 포맷팅을 정말 잘 이용하신 것 같다. 한참 부족함을 또 느꼈지만 좋은 것 배워가는 것 같다
+ eval 은 보안상 문제가 있을 수 있어서 실전에선 사용하지 않는 것이 좋다는 것도 알게 되었습니다! 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)