[프로그래머스] 수식 최대화(python 파이썬)

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

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

 

순열 문제이다. 

사실 최대 조합이 3! 이기때문에 내장된 permutation 함수를 써도 시간초과가 안나오는거같다...

 

그리고 eval라는 함수가 있는데 이 함수는 문자열 식에 대해서 계산을 해주는 함수인데 알고있었지만 쓰지 않도록 하고있는데 답을보니까 써도 시간초과가 나지 않는가보다..

 

permutation을 백트래킹을 이용하여 구하였고 문자열 계산은 stack을 이용하여 계산하였다.

 

rank = list()
max_sum = 0


def solution(expression):
    oper = list()
    if '*' in expression:
        oper.append('*')
    if '+' in expression:
        oper.append('+')
    if '-' in expression:
        oper.append('-')

    visited = [False] * len(oper)
    permutation(visited, 0, expression, oper)

    return max_sum


def permutation(visited: list, depth, expression, oper):
    if len(visited) == depth:
        calcul(rank, expression)
        return

    for i in range(len(visited)):
        if visited[i]:
            continue

        visited[i] = True
        rank.append(oper[i])
        permutation(visited, depth + 1, expression, oper)
        rank.pop()
        visited[i] = False


def calcul(rank, expression):
    global max_sum

    expression_split = list()
    temp = ''
    for s in expression:
        if s == '*' or s == '+' or s == '-':
            expression_split.append(temp)
            temp = ''
            expression_split.append(s)
        else:
            temp += s
    expression_split.append(temp)

    result = list()
    for i in range(len(rank)):
        check = False
        if i > 0:
            expression_split = result
            result = list()
        for j in range(len(expression_split)):
            if expression_split[j] == rank[i]:
                result.append(expression_split[j])
                check = True
            else:
                if check:
                    right = int(expression_split[j])
                    op = result.pop()
                    left = result.pop()
                    if op == '*':
                        result.append(left * right)
                    elif op == '+':
                        result.append(left + right)
                    elif op == '-':
                        result.append(left - right)
                    check = False
                else:
                    if expression_split[j] == '*' or expression_split[j] == '+' or expression_split[j] == '-':
                        result.append(expression_split[j])
                    else:
                        result.append(int(expression_split[j]))

    max_sum = max(max_sum, abs(result.pop()))

 

 

내장함수 eval와 permutation를 사용한 풀이

정규표현식을 사용하여 숫자를 제외한 문자를 그룹화 하여 split

expression = re.split('([^0-9])', expression)

 

import re
from itertools import permutations

def solution(expression):
    oper = list()
    if '*' in expression:
        oper.append('*')
    if '+' in expression:
        oper.append('+')
    if '-' in expression:
        oper.append('-')

    oper = list(permutations(oper))

    expression = re.split('([^0-9])', expression)
    max_sum = 0
    for ops in oper:
        expression_copy = expression[:]
        for op in ops:
            while op in expression_copy:
                op_idx = expression_copy.index(op)
                cal = str(eval(expression_copy[op_idx-1] + expression_copy[op_idx] +expression_copy[op_idx+1]))
                expression_copy[op_idx-1] = cal
                expression_copy = expression_copy[:op_idx] + expression_copy[op_idx+2:]

        max_sum = max(max_sum, abs((int(expression_copy[-1]))))

    return max_sum