[알고리즘 연습] 쇠막대기 (백준 10799, 파이썬)

쇠막대기

www.acmicpc.net/problem/10799

10799번: 쇠막대기

---

접근 및 풀이

bar_razor = list(input())
answer = 0
st = []

for i in range(len(bar_razor)):
    if bar_razor[i] == '(':
        st.append('(')

    else:
        if bar_razor[i-1] == '(': 
            st.pop()
            answer += len(st)

        else:
            st.pop() 
            answer += 1 

print(answer)

• 스택을 이용해 해결한다
• '('는 그냥 스택에 넣는다
• ')'가 나오면 두가지 경우로 나누어진다.
• ')'가 나오고 이전 문자가 '('이었다면 해당 파트는 레이저이다. 따라서 현재 stack에 쌓인 '('개수(=쇠막대기 개수)만큼 개수를 더해준다.
• ')'가 나오고 이전 문자도 ')'이었다면 쇠막대기 끄트머리에 대한 표현이다. 따라서 하나가 나올때마다 하나씩만 추가해주면 된다.
• 문제풀이 자체는 어렵지 않았지만 문제이해에 오래걸렸던 문제이다. 코딩테스트의 문제 중엔 이보다 훨씬 복잡한 문제가 많으니 문제이해능력 자체도 키울 필요성이 있겠다.