50. 수식 최대화

수식 최대화
2020 카카오 인턴십
296명 완료

레벨 2 문제답게 어려운 알고리듬을 쓰는 건 아니옵고..
주어진 식을 적절히 파싱해서
순열과 스택을 적절히 쓰면 풀리는 문제입니다. 

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

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

def solution(expression):
    from itertools import permutations
    max_nums = set()
    nums_signs_ori, signs = parse_exp(expression)
    for sign_perm in permutations(signs):
        stack = []
        nums_signs = nums_signs_ori[:]
        for sign in sign_perm:
            index = 0
            while len(nums_signs) >= 3 and index < len(nums_signs):
                if nums_signs[index] != sign:
                    stack.append(nums_signs[index])
                else:
                    if nums_signs[index] == '-':
                        stack[-1] = stack[-1] - nums_signs[index + 1]
                        index += 1
                    elif nums_signs[index] == '+':
                        stack[-1] = stack[-1] + nums_signs[index + 1]
                        index += 1
                    else:
                        stack[-1] = stack[-1] * nums_signs[index + 1]
                        index += 1
                index += 1
            if len(stack) == 1:
                max_nums.add(abs(stack[0]))
            nums_signs = stack[:]
            stack = []
    return max(max_nums)


def parse_exp(expression):
    signs = set()
    nums_signs = []
    num = ''
    for each in expression:
        if each in '0123456789':
            num = num + each
        else:
            nums_signs.append(int(num))
            num = ''
            nums_signs.append(each)
            signs.add(each)
    nums_signs.append(int(num))
    return nums_signs, signs