[BOJ] Q16638 괄호 추가하기 2

[BOJ] Q16638 괄호 추가하기 2

Question

Language: Python

Difficulty: Gold 1

전체적인 동작과정은 q16637과 유사하지만, 연산자간 우선순위가 존재하므로, 곱연산에 대한 처리를 우선적으로 해줘야한다.

processed_operands=deepcopy(remaining_operands)
processed_operators=deepcopy(remaining_operators)

index=0

#곱하기 연산 먼저 처리
while index < len(processed_operators):
    if processed_operators[index] == "*":
        processed_operators.pop(index)
        processed_operands[index]*=processed_operands[index+1]
        processed_operands.pop(index+1)
        index-=1
    index+=1

Solution

from math import inf
max_result=-inf
def calculate(op1,op2,operator):
    if operator == "+":
        return op1+op2
    elif operator =="-":
        return op1-op2
    elif operator == "*":
        return op1*op2

def processing_parenthesis_and_calculate(operands,operators):
    result=operands[0]
    for index in range(len(operators)):
        result=calculate(result,operands[index+1],operators[index])

    return result

def recursion(count,remaining_operands,remaining_operators,is_Used):
    global max_result

    if count==num:
        if is_Used:
            max_result=max(max_result,processing_parenthesis_and_calculate(remaining_operands,remaining_operators))
        #마지막 항에 대해서 괄호를 사용하지 않은 경우 마지막 피연산자도 추가한다.
        else:
            max_result=max(max_result,processing_parenthesis_and_calculate(remaining_operands+[operands[count]],remaining_operators))

        return
    #이전에 괄호를 취하지 않은 경우
    if is_Used==False:
        #현재 괄호를 취하는 경우 괄호 계산후에 해당 피연산자항 추가
        recursion(count+1,remaining_operands+[calculate(operands[count],operands[count+1],operators[count])],remaining_operators,True)
        #현재 괄호를 취하지 않는 경우 피연산자와 연사자항 추가
        recursion(count+1,remaining_operands+[operands[count]],remaining_operators+[operators[count]],False)

    #이전에 괄호를 취한 경우
    else:
        # 연산자만 추가한다.
        recursion(count+1,remaining_operands,remaining_operators+[operators[count]],False)   
         
def solution():

    for segment in expression:
        if "0"<=segment<="9":
            operands.append(int(segment))
        else:
            operators.append(segment)

    parenthesized=[False] * len(operators)
    recursion(0,[],[],False)
    
    print(max_result)
        
if __name__ == "__main__":
    length=0
    expression=""
    num=0
    operands=[]
    operators=[]

    length=int(input())
    expression=list(input())
    num=length//2 
    solution()

아니면, python의 문자열의 기반 연산을 수행하는 eval 함수를 이용하면 간편하게 연산을 수행할 수 있다.

Solution 2

from math import inf

max_result=-inf
def recursion(count,is_Used,expression):
    global max_result

    if count==num:
        if is_Used:
            max_result=max(max_result,eval(expression))
        #마지막 항에 대해서 괄호를 사용하지 않은 경우 마지막 피연산자도 추가한다.
        else:
            max_result=max(max_result,eval(expression+operands[count]))

        return
    #이전에 괄호를 취하지 않은 경우
    if is_Used==False:
        #현재 괄호를 취하는 경우 괄호 계산후에 해당 피연산자항 추가
        recursion(count+1,True,expression+"("+operands[count]+operators[count]+operands[count+1]+")")
        #현재 괄호를 취하지 않는 경우 피연산자와 연사자항 추가
        recursion(count+1,False,expression+operands[count]+operators[count])

    #이전에 괄호를 취한 경우
    else:
        # 연산자만 추가한다.
        recursion(count+1,False,expression+operators[count]) 
         
def solution():

    for segment in expression:
        if "0"<=segment<="9":
            operands.append(segment)
        else:
            operators.append(segment)

    recursion(0,False,"")
    print(max_result)

if __name__ == "__main__":
    length=0
    expression=""
    num=0
    operands=[]
    operators=[]

    length=int(input())
    expression=list(input())
    num=length//2 
    solution()