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

https://programmers.co.kr/learn/courses/30/lessons/67257?language=python3 

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

---

 문제 풀이

두 가지 방법으로 풀었다.

  1. 우선순위에 따라 후위 표기식으로 전환해 계산 (코드 1)

  2. 분할 정복을 통해서 계산 (코드 2)

 

 풀이1

문제를 보자마자 뭔가 스택으로 풀어야 할 것 같은 느낌에 바로 떠오른 것은 후위 표기법이다.

표현식에 주어진 연산자에 따른 우선순위를 만들고

우선순위에 따라 후위 표기식으로 전환한 다음 계산해 최댓값을 찾으면 된다.

def toList(expression):
    exp, op = [], []
    tmp = ''
    for ch in expression:
        if ch.isdigit(): tmp += ch
        else:
            exp.append(tmp)
            exp.append(ch)
            if ch not in op: op.append(ch)
            tmp=''
    exp.append(tmp)
    
    return exp, op

주어진 표현식을 피연산자와 연산자로 나누는 함수이다.

굳이 나눈 이유는 연산자 개수에 맞춰서 순열을 만들고 싶었다.

 

def toPost(priority, tokens):
    list_ = []
    stack = []
    
    for token in tokens:
        if token.isdigit(): list_.append(token)
        else:
            while len(stack) != 0 and priority.index(token) >= priority.index(stack[-1]): 
                list_.append(stack.pop())
            stack.append(token)
                    
    for i in range(len(stack)):
        list_.append(stack.pop())
    
    return list_

우선순위에 맞춰서 리스트로 잘라낸 표현식을 후위 표기법으로 바꾸는 함수이다.

처음에는 우선순위를 굳이 객체형으로 만들어 { '-' : 3, '*' : 2, '+' : 1} 이런 식으로 했는데

index 함수를 사용해서 객체형으로 만들지 않았다. 여기선 작은 값이 더 높은 우선순위를 가진다.

 

def calc(tokens):
    stack = []
    for token in tokens:
        if token.isdigit(): stack.append(token)
        elif len(stack) > 1 :
            b = int(stack.pop())
            a = int(stack.pop())
            if token == '*':
                stack.append(a*b)
            elif token == '+':
                stack.append(a+b)  
            elif token == '-':
                stack.append(a-b)
            
    return abs(stack.pop())

주어진 표현식을 계산해 리턴하는 함수이다.

여기서 주의해야 할 점은 우리가 200 - 100 의 계산을 원해도 스택의 특성상 그냥 순서대로 pop()하게 되면

100 - 200으로 계산된다는 점이다.

---

 풀이2

이 풀이의 핵심은 '-' > '×' > '+' 의 우선순위를 가지면 × 을 계산하기 위해선 - 의 계산이 먼저 이루어져야 하고

+ 을 계산하기 위해선 × 의 계산이 이루어져야 한다는 점이다.

이 점을 이용해 표현식을 우선순위의 역순으로 쪼개서 계산한다.

 느낀 점

내 수준보다 더 높은 수준의 문제다.. 정말 오기로 풀었다.

하지만 처음 구현할 때 후위 표기식 구현을 제대로 못했다. →  '비교 대상(A)과 스택의 Top(B)을 계속 비교한다' 

그래서 처음 구현할 때 실패해서 한참을 고민하다가 2번 풀이를 보고 최대한 이해하려고 노력했다.

해결하고 나서 다른 분의 코드를 보다가 내가 생각한 풀이법으로 푸신 분이 계셔서

내가 틀리지 않음을 알곤 바로 다시 풀었다.

많은 것을 배운 문제이다. eval() 함수, join()의 활용, 후위 표기법 복습, 스택 복습 등등

 코드1

import itertools

def toList(expression):
    exp, op = [], []
    tmp = ''
    for ch in expression:
        if ch.isdigit(): tmp += ch
        else:
            exp.append(tmp)
            exp.append(ch)
            if ch not in op: op.append(ch)
            tmp=''
    exp.append(tmp)
    
    return exp, op

def toPost(priority, tokens):
    list_ = []
    stack = []
    
    for token in tokens:
        if token.isdigit(): list_.append(token)
        else:
            while len(stack) != 0 and priority.index(token) >= priority.index(stack[-1]): 
                list_.append(stack.pop())
            stack.append(token)
                    
    for i in range(len(stack)):
        list_.append(stack.pop())
    
    return list_

def calc(tokens):
    stack = []
    for token in tokens:
        if token.isdigit(): stack.append(token)
        elif len(stack) > 1 :
            b = int(stack.pop())
            a = int(stack.pop())
            if token == '*':
                stack.append(a*b)
            elif token == '+':
                stack.append(a+b)  
            elif token == '-':
                stack.append(a-b)
            
    return abs(stack.pop())

def solution(expression):
    answer = 0
    exp, op = toList(expression)
    for priority in itertools.permutations(op, len(op)):
        answer = max(answer, calc(toPost(priority,exp)))
        
    return answer

 코드2

import itertools

def calc(priorities, n, expression):
    if n == 2: return str(eval(expression))
    if priorities[n] == '*':
        result = eval('*'.join([calc(priorities, n+1, exp) for exp in expression.split('*')]))
    if priorities[n] == '+':
        result = eval('+'.join([calc(priorities, n+1, exp) for exp in expression.split('+')]))
    if priorities[n] == '-':
        result = eval('-'.join([calc(priorities, n+1, exp) for exp in expression.split('-')]))
    return str(result)

def solution(expression):
    answer = 0
    for priorities in itertools.permutations(['+', '-', '*'], 3):
        result = int(calc(priorities, 0 ,expression))
        answer = max(answer, abs(result))
        
    return answer