잃어버린 괄호

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

 

나의 풀이

import sys
input = sys.stdin.readline

a = input().rstrip()
susi_list = []
    
num_str = ''
for i in a:
    if not i.isdigit():
        susi_list.append(int(num_str))
        susi_list.append(i)
        num_str = ''
    else:
        num_str += i
if num_str:
    susi_list.append(int(num_str))
    
while ('+' in susi_list):
    for idx in range(len(susi_list)):
        if susi_list[idx] == '+':
            susi_list[idx]  = susi_list[idx-1] + susi_list[idx+1]
            susi_list.pop(idx+1)
            susi_list.pop(idx-1)
            break
    
while len(susi_list) != 1:
    for idx in range(len(susi_list)):
        if susi_list[idx] == '-':
            susi_list[idx]  = susi_list[idx-1] - susi_list[idx+1]
            susi_list.pop(idx+1)
            susi_list.pop(idx-1)
            break
print(susi_list[0])

 

시간 복잡도

for i in a : 연산을 리스트로 만들기 ( 선형 시간 복잡도 )
while ('+' in susi_list) : '+' 가 있을때 까지 연산 수행 ( 선형 시간 복잡도 )
    내부 연산 :  ( 선형 시간 복잡도 )
해당 알고리즘 시간복잡도는 이차형 시간 복잡도 ( O(n**2) )