[Programmers] level2 - 수식 최대화 (Python) : 2020 카카오 인턴십

▶수식 최대화 - 2020 카카오 인턴십 (level 2)

▶문제

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

프로그래머스

보통은 문제를 적는데, 너무 길어서 링크로 대체하도록 하겠습니다.

 

▶제한사항

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

 

▶출력

 

입출력 예 #1
* > + > - 로 연산자 우선순위를 정했을 때, 가장 큰 절댓값을 얻을 수 있습니다.
연산 순서는 아래와 같습니다.
100-200*300-500+20 = 100-(200*300)-500+20 = 100-60000-(500+20)
= (100-60000)-520 = (-59900-520) = -60420
따라서, 우승 시 받을 수 있는 상금은 |-60420| = 60420입니다.

입출력 예 #2
->* 로 연산자 우선순위를 정했을 때, 가장 큰 절댓값을 얻을 수 있습니다.
연산 순서는 아래와 같습니다.(expression에서 + 연산자는 나타나지 않았으므로, 고려할 필요가 없습니다.)
50*6-3*2 = 50*(6-3)*2 = (50*3)*2
= 150*2 = 300
따라서, 우승 시 받을 수 있는 상금은 300입니다.

 

▶풀이

+, -, * 모든 경우에 대해서 우선순위를 작성해야 한다.

그래서 모든 경우를 한 번에 만들 수 있는 permutations를 사용해서 ops를 만들었다.

그것을 기반으로 계산을 해 result에 저장을 했고, max값을 출력하면 된다.

 

계산은 expression 하나씩 받아와서 isdigit가 True면 num에 저장을 해두고,

false면 +, -, *이기 때문에 num과 i를 arr에 넣어준다.

그다음에 stack을 이용해서 하나씩 넣고, 만약에 o와 arr에서 빼온 게 같다면 계산 값을 stack에 넣어준다.

이것을 반복하면 된다.

from itertools import permutations
    
    
def cal(exp, op):
    arr = []
    num = ''
    for i in exp:
        if i.isdigit() == True:
            num += i
        else:
            arr.append(num)
            arr.append(i)
            num = ''
    arr.append(num)
    
    for o in op:
        stack = []
        while len(arr) != 0:
            num = arr.pop(0)
            if num == o:
                n1 = stack.pop()
                n2 = arr.pop(0)
                if o == '+':
                    stack.append(str(int(n1) + int(n2)))
                elif o == '-':
                    stack.append(str(int(n1) - int(n2)))
                elif o == '*':
                    stack.append(str(int(n1) * int(n2)))
            else:
                stack.append(num)
        arr = stack
        
    return abs(int(arr[0]))
    
    
def solution(expression):
    result = []
    op = ['+', '-', '*']
    ops = list(permutations(op, 3))
    for o in ops:
        result.append(cal(expression, o))

    return max(result)

테스트가 30개가 있다. 근데 효율성 테스트는 없고 정확성 테스트만 있다.

그래서 어떻게든 정답만 도출해내면 이 문제는 통과가 될 것이다.

효율성 문제까지 있다면... 이게 정답인지는 잘 모르겠다.