[2020 카카오 인턴십 / 프로그래머스] 수식 최대화 완벽 풀이 - 파이썬(Python3)

프로그래머스 level 2 수식 최대화

-> programmers.co.kr/learn/courses/30/lessons/67257

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

이번에는 2020 카카오 인턴십에 나온 수식 최대화 문제입니다.

 

원래라면 연산 순서가  * > +,- 인데,

이 연산의 우선순위를 바꿔서

절댓값의 최댓값을 계산하는 문제입니다.

 

파이썬으로 풀면 다른 언어보다는 쉽습니다.

같이 풀어봅시다!

---

풀이 아이디어

핵심 아이디어는 우리가 원하는 우선순위로 괄호만 쳐주고, eval을 이용하면 됩니다.

만약 + > - > * 로 우선순위를 매기고싶으면

처음에 +로 묶인 묶음들에 괄호, 그다음 -로 묶인 묶음들에 괄호,

그리고 계산하면 됩니다.

 

이 구현이 까다로워서, 푼 사람이 적은 것 같습니다.

---

 

구현

문자열 길이가 그렇게 길지 않으므로, 그냥 모든 우선순위에 대해 계산을 진행하면 됩니다.

- > + > * 순으로 우선순위를 정했다면 어떻게 해야할까요?

 

"100-200+50*10+150-300*30-50+100" 으로 설명드리겠습니다.

 

먼저 *를 기준으로 나누어 리스트에 담습니다.

그럼 리스트에는 ["100-200+50", "10+150-300", "30-50+100] 이렇게 담깁니다.

 

그럼 각 원소들을 다시 - > + 의 우선순위로 계산한 뒤 각 원소들을 곱하면 됩니다.

 

리스트의 각각의 원소를 +를 기준으로 나누어 리스트에 담습니다.

그럼 리스트는 [ ["100-200", "50"], ["10", "150-300"], ["30-50", "100"] ] 이렇게 됩니다.

 

이제 가장 작은 원소들부터 계산되도록 괄호만 붙여주고, 계산은 eval함수에 맡깁시다.

일단 리스트의 2차원 원소들끼리 계산이 되어야합니다.

 

그래서 리스트의 2차원 원소들을 돌면서 "-"가 있다면 그 원소의 처음과 마지막에 괄호를 추가합니다.

[ ["(100-200)", "50"], ["10", "(150-300)"], ["(30-50)", "100"] ]

 

그다음은 리스트의 1차원 원소들을 돌면서 처음과 마지막에 괄호를 추가합니다.

[ ["((100-200)", "50)"], ["(10", "(150-300))"], ["((30-50)", "100)"] ]

 

 

이렇게 모든 요소들에 괄호를 추가하고 나면, 다시 이어붙여야합니다.

여기서는 "*", "+" 순서로 잘랐으므로 "+"를 붙이고 그다음 "*"를 붙이면 됩니다.

 

즉, 2차원 원소들을 "+"를 붙이면서 합칩니다.

[ "((100-200)+50)", "(10+(150-300))", "((30-50)+100)" ]

 

그리고 1차원 원소들을 "*"를 붙이면서 합칩니다.

"((100-200)+50)*(10+(150-300))*((30-50)+100)"

 

이제 이렇게 완성된 식을 eval에 넣어서 리턴해주면 됩니다!

 

그리고 이러한 과정을 수행하는 함수를 6가지의 우선순위에 대해 구현하면 됩니다.

근데 그냥 하나만 구현하고, 복붙해서 기호만 바꾸면 됩니다.

 

아래에 코드를 첨부합니다.

import math
def solution(expression):
    return max(map(abs, [prior1(expression), prior2(expression), prior3(expression), prior4(expression), prior5(expression), prior6(expression)]))
    

def prior1(expression):               # * > + > -
    expression = list(expression.split("-"))
    print(expression)
    for i in range(len(expression)):
        expression[i] = expression[i].split("+")
    print(expression)
        
    for i in range(len(expression)):
        for e in range(len(expression[i])):
            if "*" in expression[i][e]:
                expression[i][e] = "(" + expression[i][e] + ")"
        expression[i][0] = "(" + expression[i][0]
        expression[i][-1] = expression[i][-1] + ")"
    
    for i in range(len(expression)):
        expression[i] = "+".join(expression[i])
    
    expression = "-".join(expression)
    return eval(expression)

    
def prior2(expression):               # * > - > 
    expression = list(expression.split("+"))
    for i in range(len(expression)):
        expression[i] = expression[i].split("-")
        
    for i in range(len(expression)):
        for e in range(len(expression[i])):
            if "*" in expression[i][e]:
                expression[i][e] = "(" + expression[i][e] + ")"
        expression[i][0] = "(" + expression[i][0]
        expression[i][-1] = expression[i][-1] + ")"
    
    for i in range(len(expression)):
        expression[i] = "-".join(expression[i])
    
    expression = "+".join(expression)
    return eval(expression)

def prior3(expression):               # + > * > -
    expression = list(expression.split("-"))
    for i in range(len(expression)):
        expression[i] = expression[i].split("*")
        
    for i in range(len(expression)):
        for e in range(len(expression[i])):
            if "+" in expression[i][e]:
                expression[i][e] = "(" + expression[i][e] + ")"
        expression[i][0] = "(" + expression[i][0]
        expression[i][-1] = expression[i][-1] + ")"
    
    for i in range(len(expression)):
        expression[i] = "*".join(expression[i])
    
    expression = "-".join(expression)
    return eval(expression)

def prior4(expression):               # + > - > **
    expression = list(expression.split("*"))
    for i in range(len(expression)):
        expression[i] = expression[i].split("-")
        
    for i in range(len(expression)):
        for e in range(len(expression[i])):
            if "+" in expression[i][e]:
                expression[i][e] = "(" + expression[i][e] + ")"
        expression[i][0] = "(" + expression[i][0]
        expression[i][-1] = expression[i][-1] + ")"
    
    for i in range(len(expression)):
        expression[i] = "-".join(expression[i])
    
    expression = "*".join(expression)
    return eval(expression)

def prior5(expression):               # - > * > +
    expression = list(expression.split("+"))
    for i in range(len(expression)):
        expression[i] = expression[i].split("*")
        
    for i in range(len(expression)):
        for e in range(len(expression[i])):
            if "-" in expression[i][e]:
                expression[i][e] = "(" + expression[i][e] + ")"
        expression[i][0] = "(" + expression[i][0]
        expression[i][-1] = expression[i][-1] + ")"
    
    for i in range(len(expression)):
        expression[i] = "*".join(expression[i])
    
    expression = "+".join(expression)
    return eval(expression)

def prior6(expression):               # - > + > *
    expression = list(expression.split("*"))
    for i in range(len(expression)):
        expression[i] = expression[i].split("+")
        
    for i in range(len(expression)):
        for e in range(len(expression[i])):
            if "-" in expression[i][e]:
                expression[i][e] = "(" + expression[i][e] + ")"
        expression[i][0] = "(" + expression[i][0]
        expression[i][-1] = expression[i][-1] + ")"
    
    for i in range(len(expression)):
        expression[i] = "+".join(expression[i])
    
    expression = "*".join(expression)
    return eval(expression)