[알고리즘/백준] 10799: 쇠막대기(python)

처음에는 큐를 이용해서 풀었다. 근데 시간이 너무 오래 걸림... 방법은 '('의 갯수를 저장하고 ()을 만나면 ( 갯수만큼 더해준다. )을 만나면 막대기 한개가 끝난거라 +1을 해준다...

나중에 다른 답을 보니 스택으로 풀려있었다.

큐

from collections import deque

a = deque(list(input().replace('()', ' ')))
cnt, ans = 0, 0
while a:
    i = a.popleft()
    if i == ' ':
        ans += cnt
    elif i == '(':
        cnt += 1
    elif i == ')':
        ans += 1
        cnt -= 1

print(ans)

스택

a = list(input())
stack = []
ans = 0

for i in range(len(a)):
    if a[i] == '(':
        stack.append(1)

    else:
        stack.pop()
        if a[i-1] == '(':
            ans += len(stack)
        else:
            ans += 1
print(ans)