[알고리즘] 2020 카카오 인턴십 - 수식 최대화

2020 카카오 인턴십 - 수식 최대화

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

문제 푸는데 꽤나 시간이 걸렸다. IDE 가 없는 환경에서 시험봐야 했다면 더 오래 걸렸을 것 같다.

가장 헷갈렸던 부분은 deque 자료구조에서 특정 인덱스 값을 지우는 부분과 그 이후의 인덱스 조작에서 많이 헤맸다... 아직 내공이 많이 부족한가보다. 더 열심히 풀자!

나의 소스코드

from itertools import permutations
from collections import deque

def solution(expression):
    answer = []
    stack = deque(fill_stack(expression))
    operator = find_operator(expression)
    operator_cases =  list(permutations(operator, len(operator)))

    # 연산자 모든 조합에 대해 상금을 계산한다.
    for case in operator_cases:
        answer.append(calculate_reward_with_operator(stack, case))

    return max(answer)

# 연산자를 적용한 결과를 리턴한다.
def calculate_reward_with_operator(stack, case):
    tmp = stack.copy()

    for operator in case:
        i = 0
        while True:
            if operator not in tmp:
                break
            if tmp[i] == operator:
                front_operand = tmp[i-1]
                second_operand = tmp[i+1]
                # A * B 에서 A 삭제 (연산자 *, -, + 가능)
                del tmp[i-1]
                # A * B 에서 B 삭제 (연산자 *, -, + 가능)
                del tmp[i]

                # 피연산자를 연산자에 맞게 계산한 뒤 tmp 배열에 다시 넣는다.
                if operator == '*':
                    tmp.insert(i-1, int(front_operand) * int(second_operand))
                elif operator == '-':
                    tmp.insert(i-1, int(front_operand) - int(second_operand))
                elif operator == '+':
                    tmp.insert(i-1, int(front_operand) + int(second_operand))

                # 연산자 제거
                del tmp[i]
                i = 0
            i += 1
    # 리턴 전에 절댓값 적용
    tmp = list(map(abs, tmp))
    return max(tmp)            

# 스택에 ["100", "-", "200", "*", "300"] 형태로 파싱하여 채워넣어 리턴한다.
def fill_stack(expression):
    tmp = ''
    stack = []
    for ch in expression:
        if ch.isdigit():
            tmp += ch
        else:
            stack.append(tmp)
            stack.append(ch)
            tmp = ''
    stack.append(tmp)
    return stack

# expression에서 연산자를 찾고 중복되는 연산은 제거하여 리턴한다.
def find_operator(expression):
    operator = []
    for ch in expression:
        if not ch.isdigit():
            operator.append(ch)
    operator = list(set(operator))
    return operator

print(solution("100*100-99*100"))