[프로그래머스] 수식 최대화 (Python 파이썬)

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

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

문제 설명

문제의 설명이 굉장히 길어 위 링크를 참고하시는 것을 추천드립니다.

 

수식 ex ("100-200*300-500+20") 이 주어졌을 때 +, -, *의 우선순위를 매번 다르게 하여 나타나는 값들 중 최댓값을 구하는 문제입니다.

 

원래는 * > +,- 의 우선순위를 갖지만, 이 문제에서는 *>+>- 가 될 수도 있고 +>->* 가 될 수도 있습니다.

---

풀이 과정

permutations(순열)을 통해 "*", "+", "-"로 만들 수 있는 우선순위 3! = 6 가지에 대해 수행합니다.

 

먼저 문자열 수식을 숫자와 기호로 분리를 해주기 위해

수식(expression)을 처음부터 끝까지 돌면서 리스트로 분리합니다. ( ["100", "-", "200", "*" ...] 이런 식으로 나오도록 )

 

그 다음, 리스트를 돌면서 해당 우선순위에 맞게 수식 계산을 하면 됩니다.

예시로, 가장 처음 우선순위가 ["*", "+", "-"] 라고 한다면, 리스트를 돌다가 *를 만나면 *의 앞뒤 숫자를 곱해줍니다.

(곱하기를 한 후에는 곱했던 수들을 제거해줘야 하기 때문에 앞 뒤 수를 제거합니다)

 

*를 끝냈다면 그 다음 +를 만나면 같은 방식으로 계산을 해주면 됩니다. 그 다음은 "-"에 대해 수행하고...

 

이렇게 한 우선순위에 대해 계산을 마쳤다면 최댓값을 저장합니다.

이렇게 첫 번째 우선순위 ["*", "+", "-"]에 대해 수행을 완료했다면, 다음 우선순위로 넘어가서 다시 반복하면 됩니다.

from itertools import permutations

def solution(expression):
    answer = 0
    oper = ["*", "+", "-"]
    mymax = int(-1e9)

    for per in permutations(oper, 3):
        perm = list(per)
        exp = ''
        tmp = []
        for i in range(len(expression)):
            if str(0) <= expression[i] <= str(9):
                exp += expression[i]
            else:
                tmp.append(exp)
                tmp.append(expression[i])
                exp = ''
            if i == len(expression) - 1:
                tmp.append(exp)


        for j in range(len(perm)):
            i = 0
            while i < len(tmp):
                if tmp[i] == perm[j]:
                    tmp[i-1] = eval(str(tmp[i-1])+perm[j]+str(tmp[i+1]))
                    del tmp[i]
                    if i < len(tmp):
                        del tmp[i]
                else:
                    i+=1

        mymax = max(mymax, abs(tmp[0]))
        
    return mymax

print(solution("100-200*300-500+20"))

https://github.com/HongEunho 

HongEunho - Overview

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !