10799번 쇠막대기 파이썬

문제:www.acmicpc.net/problem/10799

10799번: 쇠막대기

처음에 문제를 풀 때 '()'를 'l'로 치환을 한 다음에 두개의 리스트를 만들고 하나의 리스트에는 ')'를 만나기 전까지의 문자를 저장하였고 나머지 리스트는 ')'를 만났을 때 '('를 만나기 전까지의 'l'의 갯수를 센 다음에 저장을 하고 초기화하는 방식으로 풀었다. 그런데 그 결과는 '시간 초과'라는 결과를 가져왔다.  그렇게 된 이유는 최악의 경우에 시간 복잡도가 N^2이기 때문이다. 

import sys
script = sys.stdin.readline().rstrip()
script = script.replace("()","l")
stk=[]
razer=[]
ret=0
for x in script:
    if x=='(':
        stk.append('(')
    elif x=='l':
        if len(stk)!=0:
            stk.append('l')
    elif x==')':
        while stk[-1]!='(':
            if len(stk)==0:
                break
            elif stk[-1]=='l':
                razer.append(stk.pop())
        if stk[-1]=='(':
            stk.pop()
            ret+=len(razer)+1
            stk+=razer
            razer=[]
print(ret)

 

참고:ilgls1.tistory.com/16

[Python] 백준 10799 쇠막대기

그래서 풀다가 결국 어떻게 나아가야 할 지 몰라서 검색해서 위의 블로그를 통해 풀이를 참고했다.

')'가 나왔는데 그전의 문자가 '('이냐 또는 ')'인 경우에 따른 경우의 수를 둬서 문제를 해결하였다.

 

val = input()
sum=0
left=0
for i in range(len(val)):
    if val[i]=='(':
        left+=1
    elif val[i]==')':
        left-=1
        if val[i-1]=='(':
            sum+=left
        else:
            sum+=1
print(sum)