[2020 카카오 인턴십] 수식 최대화

 

코딩테스트 연습 - 수식 최대화

 

풀이

 다음과 같은 과정을 통해서 답을 구할 수 있다. 

1. 수식에 존재하는 연산자 리스트를 구한다.
2. 순열을 통해서 연산자들의 우선순위를 정해준다.
3. 각각의 우선순위에 따라서 입력 받은 중위 표현식으로 된 수식을 후위 표현식으로 변환한다.
4. 변환한 후위 표현식을 계산하여 결괏값을 구하고 이중 최댓값을 구한다.

 

코드

from itertools import permutations

# 중위 표기식을 후위 표기식으로 변환하는 함수
# priority는 연산자의 우선순위를 나타낸다. 앞에 있을수록 우선순위가 높음을 의미한다. 
# 리턴 값은 후위 표기식의 리스트 형태
def toPostfix(expression, priority):
    num = ''
    result = [] # 후위 표기식으로 변환한 결과 
    opStack = [] # expression에서 마주쳤던 연산자를 넣어놓는 연산자 스택

    for e in expression:
        if e not in '+-*': # 숫자에 해당할 경우 num 문자열에 이어 붙인다.
            num += e
        else: # 연산자일 경우 
            result.append(int(num)) # 이전까지 만들었던 num은 후위 표기식에 append
            num = '' # num 변수 초기화 

            # 작거나 같으면 팝
            while len(opStack) != 0:
                opPriority = priority.index(e) # 현재 연산자의 우선순위
                topOpPriority = priority.index(opStack[-1]) # opStack의 top에 있는 연산자의 우선순위
                
                # 현재 연산자의 우선순위보다 opStack의 top에 있는 연산자의 우선순위가 작거나 같을 경우
                # 후위 표기식에 opStack의 top에 있는 연산자를 추가한다.
                if topOpPriority <= opPriority: 
                    result.append(opStack.pop())
                else: # 그렇지 않은 경우 while문 종료
                    break

            opStack.append(e) # 현재 연산자를 opStack에 넣어준다.

    if num != '': # 마지막 숫자를 후위 표기식에 넣어준다.
        result.append(int(num))

    while len(opStack) != 0: # 남은 연산자들을 후위 표기식에 추가한다. 
        result.append(opStack.pop())

    return result 


# 입력으로 받은 후위 표기식으로 결괏값을 계산한다.
def compute(postfix):
    st = [] # 숫자를 담아두기 위한 스택 

    for p in postfix:
        # 연산자일 경우 스택에서 숫자 두 개를 꺼내어 계산한다.
        # 계산한 결괏값은 다시 스택에 넣어준다.
        if p in ['+', '-', '*']: 
            rightOperand = st.pop()
            leftOperand = st.pop()

            if p == '+':
                st.append(leftOperand + rightOperand)
            elif p == '-':
                st.append(leftOperand - rightOperand)
            else:
                st.append(leftOperand * rightOperand)
        else:
            st.append(p)

    # 스택에 남아 있는 숫자가 후위 표기식을 계산한 최종 결괏값이 된다. 
    return abs(st[0])


def solution(expression):
    answer = 0
    operators = [] # 연산자 리스트

    for op in ['+', '-', '*']:
        if expression.find(op) != -1: # 표현식에 있는 연산자를 operators 리스트에 넣어준다.
            operators.append(op)

    # 순열 연산을 통해서 연산자들의 우선순위 경우의 수를 모두 체크한다.
    for priority in permutations(operators, len(operators)):
        converted = toPostfix(expression, priority) # 우선순위에 따라 후위 표기식으로 변환
        answer = max(answer, compute(converted)) # 변환을 통해 얻은 후위 표기식을 계산하여 큰 값을 answer에 넣어준다.

    return answer