[카카오 인턴십/프로그래머스] 수식 최대화 - Python

코딩테스트 연습 - 수식 최대화 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

 

문제 설명

해커톤 대회에 참가하는 모든 참가자들에게는 숫자들과 3가지의 연산문자(+, -, *) 만으로 이루어진 연산 수식이 전달되며, 참가자의 미션은 전달받은 수식에 포함된 연산자의 우선순위를 자유롭게 재정의하여 만들 수 있는 가장 큰 숫자를 제출하는 것입니다.
연산자의 우선순위를 새로 정의할 때, 같은 순위의 연산자는 없어야 합니다.

수식에 포함된 연산자가 연산자가 3개라면 3! = 6가지 조합이 가능합니다.

같은 연산자끼리는 앞에 있는 것의 우선순위가 더 높습니다.
만약 계산된 결과가 음수라면 해당 숫자의 절댓값으로 변환하여 제출합니다.

제출한 숫자가 가장 큰 참가자를 우승자로 선정하며, 우승자가 제출한 숫자를 우승상금으로 지급하게 됩니다.

 

- 매개변수 : 참가자에게 주어진 연산 수식이 담긴 문자열 expression

- return 값 : 우승 시 받을 수 있는 가장 큰 상금 금액

 

 

문제 풀이

- 연산자를 permutations로 우선순위 결정 (어차피 연산자가 최대 3개)

- 연산자 우선순위가 낮은 연산자를 기준으로 식을 split하고 재귀적으로 계산

** calc 함수에서 중간 eval 계산 후 str을 해주어야한다. 연산자가 남아있지 않은 return의 경우에는 필요가 없다고 생각했는데 재귀호출이 되어서 연산자가 있는 경우에 에러가 발생한다. 마지막 solution 함수에서 int로 변환해주면 된다.

from itertools import permutations

# 우선순위가 낮은 연산자를 기준으로 split 진행
def calc(prior, n, exp):
    # 연산자가 없는 식의 경우
    if exp.isdigit(): return str(exp)
    
    # 연산 수행
    if prior[n] == '+':
        tmp1 = exp.split('+')
        res = []
        for tmp in tmp1:
            res.append(calc(prior, n+1, tmp))  # 재귀
        return str(eval('+'.join(res))) # 가장 낮은 우선순위 연산자 계산
    
    if prior[n] == '-':
        tmp1 = exp.split('-')
        res = []
        for tmp in tmp1:
            res.append(calc(prior, n+1, tmp))
        return str(eval('-'.join(res)))
    
    if prior[n] == '*':
        tmp1 = exp.split('*')
        res = []
        for tmp in tmp1:
            res.append(calc(prior, n+1, tmp))
        return str(eval('*'.join(res)))
            

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

 

 

< 함수 정리 >

- eval : 매개변수로 받은 expression을 문자열로 받아서 결과값 리턴

- isdigit : 문자열이 숫자(digit)로만 구성되어있으면 true를 리턴