[Programmers] - 수식 최대화 (2020 카카오 인턴십) with Python

📎 간략한 문제 정리

• 기존 사칙연산의 연산자 우선순위가 아니라 임의로 연산자 우선순위를 정해 주어진 expression의 연산을 합니다. 연산 결과의 절대값 중 가장 큰 값을 반환합니다.

 

📈 문제 분석

• 이 경우 모든 경우를 탐색하는 Brute-Force(완전 탐색)을 통해 최적의 결과를 찾아냅니다.

 

🙋‍♂️ 내가 처음 생각한 해결 방법

• 기존의 제 풀이는 연산자 우선순위대로 탐색하며 연산을 진행하고, 다음 연산자를 검색하며 다음 연산을 진행하는 방식으로 결과를 찾았습니다. 하지만 공부를 위해 이 문제를 새로 풀며 중위 표기를 후위 표기로 바꾸는 과정에 연산자 우선순위가 있음을 기억했고 그 연산자 우선순위 표만 바꾸는 구조로 작성하면 되므로 중위를 후위로 바꾸는 메소드 한개, 후위 연산을 계산하는 메소드 한개를 추가로 만들어 모든 경우 탐색을 했습니다. 중위 연산을 후위 연산으로 만드는 방법을 공부해보기 위해 새로운 코드를 짰습니다.

 

💻 풀이한 코드

 

⌚️ 예전 풀이

 

from itertools import permutations
import math

# 리스트의 내용물을 편집할 때 길이가 바뀔 때에는 직접 리스트를 편집하는 것은 좋지 않다.

def solution2(expression):
    # 연산자의 우선 순위 정하기
    # expression을 순회하며 존재하는 연산자를 확인한다.
    opers = []
    for i in range(len(expression)):
        # 만약 i번째 요소가 연산자이면 연산자를 opers에 저장한다.
        if not expression[i].isdecimal() and expression[i] not in opers:
            opers.append(expression[i])
    # 연산자 우선순위를 결정한다.
    opers_priority = list(permutations(opers, len(opers)))
    # expression을 연산자를 기준으로 나눈다.
    idx = 0
    temp = []
    splited_expression = []
    # expression을 연산자를 기준으로 나누어 저장한다.
    while True:
        # 숫자이면 임시저장소에 저장
        if expression[idx].isdecimal():
            temp.append(expression[idx])
            # 마지막 요소라면 뒤에 연산자가 없으므로 바로 넣어주고 종료한다.
            if idx == len(expression)-1:
                splited_expression.append(''.join(temp))
            idx += 1
        # 연산자이면 기존에 저장되있던 요소와 연산자를 각각 splited_expression에 저장한다.
        else:
            splited_expression.append(''.join(temp))
            splited_expression.append(expression[idx])
            temp = []
            idx += 1
        # 끝까지 도달하면 종료
        if idx == len(expression):
            break
    max_val = -math.inf
    for i in range(len(opers_priority)):
        # 연산자 우선순위가 결정된 리스트
        order = opers_priority[i]
        temp_list = splited_expression[:]
        # 연산자 결정
        for j in range(len(order)):
            idx = 0
            while idx<len(temp_list):
                if temp_list[idx] == order[j]:
                    temp_list = temp_list[:idx-1]+[str(eval(''.join(temp_list[idx-1:idx+2])))]+temp_list[idx+2:]
                else:
                    idx += 1
        if abs(int(temp_list[0])) > max_val:
            max_val = abs(int(temp_list[0]))
    return max_val

 

🙋 새로운 풀이

 

def solution(expression):
    from itertools import permutations
    operations = [1, 2, 3]
    operation_priorities = list(permutations(operations, 3))
    priority_dict = {}
    result = 0
    for priority in operation_priorities:
        priority_dict["+"] = priority[0]
        priority_dict["-"] = priority[1]
        priority_dict["*"] = priority[2]
        oper_result = int(calculate_with_suffix(infix_to_suffix(expression, priority_dict)))
        result = max(abs(oper_result), result)
    return result

def infix_to_suffix(infix, priority):
    suffix = []
    stack = []
    temp = ""
    for token in infix:
        if token.isnumeric():
            temp += token
        else:
            suffix.append(temp)
            temp = ""
            if not stack or priority[stack[-1]] < priority[token]:
                stack.append(token)
            else:
                while stack:
                    if priority[stack[-1]] >= priority[token]:
                        suffix.append(stack.pop())
                    else:
                        break
                stack.append(token)
    suffix.append(temp)
    suffix.extend(stack[::-1])
    return suffix

def calculate_with_suffix(suffixes):
    stack = []
    for suffix in suffixes:
        if suffix.isdecimal():
            stack.append(suffix)
        else:
            latter = stack.pop()
            former = stack.pop()
            stack.append(str(eval(former+suffix+latter)))
    return stack[-1]

 

📝 해결 과정에서 만난 문제, 고민들

• 괄호의 존재 여부:
• 일반적으로 인터넷에 구현된 중위표현을 후위표현으로 바꾸는 메소드는 괄호가 존재합니다. 그래서 구현 방식에 차이를 줘야했지만 생각해보면 중위표현은 ISP, ICP로 스택 내에서 우선순위, 스택 바깥에서 우선순위에 괄호가 포함되어 있습니다. 그래서 괄호를 특별 취급하지않고 우선순위만 따져 로직을 작성했습니다.
• 중위 표현식에서 연산자가 나왔을 때 stack의 top과 비교시:
  
• 의 경우 '-' 연산자의 우선순위가 곱하기 연산보다 낮기 때문에 곱하기 연산자를 pop해야 합니다. 그 다음 '+'의 경우 '-' 연산자와 우선순위가 같은데 이 경우도 '-' 연산자의 우선순위보다 '+' 연산자의 우선순위가 '작지 않기 때문에' pop 합니다. 이것을 생각해보면 stack에서 pop 하는 경우는 토큰 연산자, 이 경우 '-' 연산자보다 먼저 연산되야 하는 경우인데 연산자 우선순위가 같은 경우 먼저 존재하는 연산이 먼저 진행되어야 하므로 pop 하는 것을 알 수 있습니다.
• 인터넷의 예시들은 보통 연산자 종류를 다양하게 만들어 stack의 top과 토큰 연산자의 우선순위가 달랐습니다. 하지만 연산자 우선 순위가 같은 경우는 찾기 힘들었습니다. 이 문제의 경우 연산자 우선순위가 같은 경우가 존재하지 않지만 학습을 위해 생각해보았습니다. 로직을 고민해본 결과 토큰 연산자의 우선순위가 stack의 top보다 클 때에만 stack에 토큰 연산자를 pop 없이 push하므로 같은 경우는 top의 연산자의 우선순위가 더 큰 경우처럼 pop 해줍니다. 예를 들어

 

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