16637번 / 괄호 추가하기 - 파이썬

https://www.acmicpc.net/problem/16637

16637번: 괄호 추가하기

 

소스코드

def calcpart(n1,n2,ex):
    if ex == '+':
        return n1+n2
    elif ex == '-':
        return n1-n2
    elif ex == '*':
        return n1*n2


def recursive(numQue,exQue,start):
    commands = []
    def generate(numQue,start,init_command):
        if start >= len(numQue):
            #print(init_command)
            commands.append(init_command[:])
            return
        #no 괄
        init_command.append(0)
        generate(numQue,start+1,init_command)
        init_command.pop()

        #add 괄
        if start < len(numQue)-1:
            init_command.append(1)
            init_command.append(0)
            generate(numQue,start+2,init_command)
            init_command.pop()
            init_command.pop()
    generate(numQue,start,[])
    return commands

def calc_3(commands):
    for command in commands:
        tNumQue = rnumQue[:]
        tExQue = rexQue[:]
        # print("command:" ,command)
        for i in range(len(command)-1,-1,-1):
           if command[i] == 1:
                n1,n2 = tNumQue.pop(i),tNumQue.pop(i)
                ex = tExQue.pop(i)
                tNumQue.insert(i,calcpart(n1,n2,ex))
           # print("tNumQue", tNumQue)
           # print("tExQue", tExQue)
           global answer
           answer = max(answer, calc_4(tNumQue, tExQue))

def calc_4(ttNumQue,ttExQue):
    tNumQue = ttNumQue[:]
    tExQue = ttExQue[:]
    sums = tNumQue.pop(0)
    while len(tExQue) != 0:
        tEx = tExQue.pop(0)
        if tEx == '+':
            sums += tNumQue.pop(0)
        elif tEx == '-':
            sums -= tNumQue.pop(0)
        elif tEx == '*':
            sums *= tNumQue.pop(0)
    # print(sums)
    return sums
N = int(input())
stream = input()
rnumQue = []
rexQue = []
for ch in stream:
    if ch == '+' or ch == '-' or ch == '*':
        rexQue.append(ch)
    else:
        rnumQue.append(int(ch))
answer = -9 ** 10
if N == 1 or N==3:
    print(max(eval(stream),answer))
else:
    allCommand = recursive(rnumQue,rexQue,0)
    calc_3(allCommand)
    print(answer)

 

고려해야 할 것들

1. 괄호를 넣는 경우 구하기

2. [1]에서 구한 경우 계산하기

 

[1]의 경우 recursive()에서 모든 경우의 수를 구해 commands에 넣어 return 해줬다. 

[2]의 경우 문제 조건 때문에 상다아앙히 화났다. 문제 조건에서 연산자별 우선순위가 없다고 했기 때문에 여기서 3시간은 쓴듯 하다. 문제를 똑바로 읽자

 

모든 경우의 수를 구할때 간단하게 여는 괄호가 있는 숫자를 1로 표현했다. command = [1,0,0,0,0]이라면 (3+8)*9-2+7인 것이다. 저런 command를 모두 구했지만 이걸 계산하는게 너무 힘들었다...

 

eval() 내장 라이브러리를 사용하려고 최대한 stream으로 수식을 표현해봤는데 eval은 연산자에 우선순위가 있어 절대로 하면 안될 짓이었다.  그래서 그냥 numQue, exQue를 조작하고 계산해주는 방법을 썼다... 진작 이럴걸!

 

그리고 넘겨준 numQue, exQue도 어떻게 계산해야 깔끔할까 고민한 시간이 길었다.