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

<문제 유형>

 -> 분할정복 

   ; 예전부터 분할 정복에 약하다 생각했지만 이번 문제를 마주했을 때 분할 정복/ 재귀 개념을 떠올리지 못해서 

   더 많은 연습이 필요하다고 느낀 문제이다. 

 

<해결 알고리즘>

0. +/-/* 연산자의 우선순위 순서는 총 6개이며 각 우선순위 배열에 따른 연산 결과를 계산한다

  prior = [
        '*+-', '*-+',
        '+*-', '+-*',
        '-*+', '-+*' ]

1. 우선순위가 낮은 연산자 순서부터 split(연산자) 를 통해 문자열을 분리한다 

2. 분리된 문자열을 다시 재귀적으로 그 다음 우선순위가 낮은 연산자를 기준으로 분리한다 

3. 우선순위가 가장 높은 연산자까지 문자열 분리가 모두 완료되었다면 우선순위가 높은 순서대로 연산을 진행하며 재귀를 하나씩 탈출한다  

4, 해당 우선순위 배열에 따른 연산의 결과가 최댓값보다 크면 갱신, 6가지 우선순위 배열 모두 마친뒤 최댓값을 출력 

 

SOURCE CODE : 

---

# 분할정복 -> 재귀로 작은 문제들로 나눠서 재귀 탈출하면서 최종 연산 결과 도출 
def calc(expression, op, depth):
	#세번째(마지막) 연산자까지 재귀 돌았으면 우선순위 연산 진행 후 재귀 탈출
    if depth == 2:
        tmp = expression.split(op[2]) # expression이 숫자 하나로만 이루어진 경우 그 숫자 리턴 
        if len(tmp) == 1:
            return int(tmp[0])
        
        #연산 우선순위 가장 높은 연산 진행 후 그 결과 리턴, 이때 해당 연산자가 여러개 포함될 수 있으므로 tmp에 
        # 숫자들 담아서 연산자의 갯수만큼 연산해서 모두 더한값 리턴 
        result = int(tmp[0])
        for i in range(1, len(tmp)):
            if op[2] == "+":
                result = result + int(tmp[i])
            elif op[2] == "-":
                result = result - int(tmp[i])
            else:
                result = result * int(tmp[i])

        return result 
    
    # 마지막 연산자가 아직 아닌 경우, 해당 연산자로 문자열 나누고 
    # 그 문자열의 재귀문 돌린 결과값들을 이용한 연산값 리턴  
    tmp = expression.split(op[depth])
    result = calc(tmp[0], op, depth+1)
    for i in range(1, len(tmp)):
        if op[depth] == "+":
            result = result + calc(tmp[i], op, depth+1)
        elif op[depth] == "-":
            result = result - calc(tmp[i], op, depth+1)
        else:
            result = result * calc(tmp[i], op, depth+1)
    return result 
  
    
def solution(expression):
    answer = 0
    
    prior = [
        '*+-', '*-+',
        '+*-', '+-*',
        '-*+', '-+*'
    ]
    
    max_result = 0
    # 6가지 연산 순서에 따른 결과 iteration
    for op in prior:
        result = abs(calc(expression, op, 0))
        max_result = max(max_result, result)
    
    answer = max_result
    return answer