쇠막대기(스택)

인프런 김태원님의 파이썬 알고리즘 문제풀이 강의를 듣고 작성한 글입니다.

https://inf.run/k3z6

파이썬 알고리즘 문제풀이 (코딩테스트 대비) - 인프런 | 강의

내 풀이 ( 정답 아님 )

s = input()
stack = []
res = 0

for i in s:
    if i == "(":
        stack.append(i)
    else:
        #이 부분이 오류인데 stack[-1]을 하면 닫힌 괄호가 연속일때 count 할 수 없음
        if stack[-1] == "(":
            stack.pop()
            res += len(stack)
        else:
            stack.pop()
            res += 1

print(res)

주석 부분의 if stack[-1] 이 오류였다.
stack에는 열린괄호만 들어가는데
닫힌괄호 전의 괄호를 확인하기 위해서는

stack[-1] 이 아니라 문자열의 s[i-1]을 해야한다.

 

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

이 문제를 푸는 방법은

( 열린괄호일때는 stack에 append하고

) 닫힌괄호일때는 stack에서 pop 하여 쇠막대기의 개수만큼 + 해준다.
이때 닫힌괄호 앞의 괄호가 중요한데,
) 닫힌괄호 앞의 괄호가 ( 열린괄호이면 스택의 남아있는 열린괄호가 쇠막대기 개수이고,
) 닫힌괄호 앞의 괄호가 ) 닫힌괄호이면 막대기의 끝이므로 +1 만 해준다.