[문제 풀이] 수식 최대화

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

 

해결 과정

리스트 조작으로 인해 시간 소요 생각보다 많이 됐던 문제.

string 으로 주어진 식에 대해서 조작하는 과정이 있는 문제다.

근데 다른 풀이 보니 더 간단하게 푼 풀이가 많은 것 같아서 참고해보자.

 

생각의 흐름

1. 연산자 뽑기 

2. 연산자로 가능한 순열 뽑기 (가짓수는 최대 6개이므로 전부다 계산하는 문제구나)

3. 계산해주는 함수 만들기 (이 부분 좀 더 쉽게 할 수 없을까)

 3-1. 이를 위해 연산자, 피연산자로 분리된 리스트 만들기

4. 계산 결과 값 중 가장 최댓값 뽑기

나의 풀이

 

from itertools import permutations

def calculate(elements, operators):  # operates == ('*', '-', '+')
    all_elements = elements
    result = 0
    
    for operator in operators:
        while len(all_elements) != 1:
            for i, element in enumerate(all_elements):
                if element == operator:
                    a = all_elements[i-1]
                    b = all_elements[i+1]
                    if operator == "*":
                        all_elements.insert(
                            i+2, a * b)
                    elif operator == "-":
                        all_elements.insert(
                            i+2, a - b)
                    elif operator == "+":
                        all_elements.insert(
                            i+2, a + b)
                    del all_elements[i-1]
                    del all_elements[i-1]
                    del all_elements[i-1]
                    break
            if operator not in all_elements:
                break
    result = all_elements[0]
    return result

def solution(expression):
    answer = 0
    # 연산자 뽑기
    operators = []
    elements = []
    last_operator_index = -1
    for index, value in enumerate(expression):
        if value == "-" or value == "*" or value == "+":
            operators.append(value)
            
            elements.append(int(expression[last_operator_index + 1:index])) 
            elements.append(value)

            last_operator_index = index
    elements.append(int(expression[last_operator_index + 1:]))

    operators = list(set(operators))
    operator_combi = list(permutations(operators, len(operators)))
    # 계산해서 최댓값 뽑기
    candidates = [abs(calculate(elements[:], i)) for i in operator_combi]
    answer = max(candidates)
    return answer

 

다른 풀이

 

def solution(expression):
    operations = [('+', '-', '*'),('+', '*', '-'),('-', '+', '*'),('-', '*', '+'),('*', '+', '-'),('*', '-', '+')]
    answer = []
    for op in operations:
        a = op[0]
        b = op[1]
        temp_list = []
        for e in expression.split(a):
            temp = [f"({i})" for i in e.split(b)]
            temp_list.append(f'({b.join(temp)})')
        answer.append(abs(eval(a.join(temp_list))))
    return max(answer)

음 이건 생각하기 어려운 풀이인 듯. 디버깅 하면서 어떤 원리인지 파악했다. 

eval() 함수를 쓸 건데, 아예 연산자 우선순위 별로 괄호를 쳐서 통째로 eval() 함수에 넣는 풀이이다. 

가령 

('+', '-', '*')

계산할 식 => 100-200*300-500+20

 

1) 연산자 우선순위 => ('+', '-', '*')

((100)-(200*300)-(500))+((20))

 

2) 연산자 우선순위 => ('+', '*', '-')

((100-200)*(300-500))+((20))

import re
from itertools import permutations

def solution(expression):
    #1
    op = [x for x in ['*','+','-'] if x in expression]
    op = [list(y) for y in permutations(op)]
    ex = re.split(r'(\D)',expression)

    #2
    a = []
    for x in op:
        _ex = ex[:]
        for y in x:
            while y in _ex:
                tmp = _ex.index(y)
                _ex[tmp-1] = str(eval(_ex[tmp-1]+_ex[tmp]+_ex[tmp+1]))
                _ex = _ex[:tmp]+_ex[tmp+2:]
        a.append(_ex[-1])

    #3
    return max(abs(int(x)) for x in a)

re를 알았다면 조금 더 간결하게 작성할 수 있는 코드. 

이게 그나마 이해하기 용이한 코드. 

 

 

IDEA

python의 mutable 객체

python의 list는 mutable(가변) 객체이다. call by reference처럼 동작한다. list를 매개변수로 넘겨줄 때, 그 리스트 자체가 바뀌게 되므로 원본 list를 바꾸고 싶지 않는 경우에는 list[:] 이런 식으로 새로운 변수를 넘겨주거나 새로운 변수를 재정의 해줘야 한다. 

 

eval(expression)

'100*200' -> 20000 이런 결과를 바로 얻고 싶을 때 eval() 함수를 사용할 수 있다. 

 

import re, 정규표현식

'100*200-300' 이 문자열을 ['100', '*', '200', '-', '300'] 이렇게 쪼개서 리스트에 저장하고 싶을 때 re.split을 사용할 수 있다.