[Algorithm] 쇠막대기

자료구조에서 배웠던 괄호검사가 생각나서 스택을 사용하여 구현해야겠다고 생각했다.

<내 답안>

li = list(map(str, input()))
tmp = []
cnt = 0
for i in range(len(li)):
    if li[i] == '(':
        tmp.append(li[i])

    else:
        if tmp[-1] == ')':
            tmp.append(li[i])
            cnt += 1
        else:
            tmp.pop()
            cnt += tmp.count('(')

print(cnt)

'('가 나오면 무조건 스택에 넣고, ')'가 나오면 바로 전 자료가 무엇인지 확인하고 '('면 레이저이기 때문에 pop 시켜서 스택에서 빼고 조각(cnt)를 증가시켰다. ')'면 그냥 넣고 조각(cnt)은 증가시켰다. 여기서 내가 실수한 부분이 있다. ')' 일 때 바로 전 자료가 ')'이면 그냥 append 시켰는데 그래서 스택 내부의 자료가 꼬였다. 스택에는 ')'가 들어가면 안됐다. 여기서 ')'는 쇠막대의 마지막 지점을 의미하기 때문에 쇠막대의 첫 부분('(') 을 pop 시켜서 쇠막대 자체를 스택에서 지워야 했다.
또한 tmp[-1] == ')' 로 확인하면 안된다. 스택에는 애초에 ')'이 들어가지 않는다. li[i-1]으로 바꿔서 바로 전 자료를 이렇게 표시해야 한다.

<모범답안>

s = input()
stack = []
cnt = 0
for i in range(len(s)):
    if s[i] == '(':
        stack.append(s[i])
    else:
        stack.pop()
        if s[i-1] == '(':
            cnt += len(stack)
        else:
            cnt += 1
print(cnt)