2020 카카오 인턴십 수식 최대화 풀이 With Python

문제 링크: https://programmers.co.kr/learn/courses/30/lessons/67257

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

실제 시험 당시에는 DFS를 사용하여 풀었던 거 같은데 기억이 잘 나지 않아서 문제를 새롭게 풀어보려 노력하였습니다. 먼저 수식의 표현을 숫자와 연산자로 구분하고자 숫자일 경우 문자열에 계속 더하고, 연산자를 만날 경우 더해준 문자열을 int형식으로 바꾸어 새로운 리스트에 추가하였고, 연산자도 추가하였습니다. 이렇게 할 경우 마지막에 숫자 문자열 값이 남으므로 마지막 숫자 문자열 또한 int형식으로 바꾸어 추가하였습니다. 이후에  연산자인 +,*,-에 대한 우선순위를 부여하고자 itertools 모듈에서 permutations 함수를 가져와 사용하였습니다. 각 우선순위의 경우마다 리스트 원소의 조작이 필요하므로 copy모듈에서 deepcopy 함수 또한 가져와 사용하였습니다. 이후에는 각 우선순위마다 우선순위 연산자를 만났을 때 연산을 통해 결괏값을 리스트에 추가하였고, 리스트의 원소가 1개 남았을 경우에 정답 값과 비교하여 더 큰 값을 정답 값으로 경신하였습니다.  소스코드는 아래와 같습니다. 

from itertools import permutations
from copy import deepcopy


def solution(expression):
    answer = 0
    new1 = []
    sub = ''
    for i in expression:
        if i == '+' or i == '-' or i == '*':
            new1.append(int(sub))
            sub = ''
            new1.append(i)
        else:
            sub += i
    new1.append(int(sub))
    for i in permutations(['*', '+', '-']):
        order = i
        flag = 0
        new = deepcopy(new1)
        for op in order:
            idx = 1
            while 1:
                if idx >= len(new):
                    break
                elif new[idx] == op:
                    if op == '-':
                        new[idx] = new[idx - 1] - new[idx + 1]
                    elif op == '+':
                        new[idx] = new[idx - 1] + new[idx + 1]
                    else:
                        new[idx] = new[idx - 1] * new[idx + 1]
                    new = new[:idx - 1] + [new[idx]] + new[idx + 2:]
                    if len(new) == 1:
                        answer = max(answer, abs(new[0]))
                        flag = 1
                        break

                else:
                    idx += 1
            if flag:
                break
    return answer

소스코드에 대한 질문이 있으시면 댓글 남겨주시면 답변드리겠습니다. 읽어주셔서 감사합니다. :-)