[백준/파이썬] 10799 쇠막대기 (자료 구조) - 스택 사용하기

➰ 10799번 쇠막대기

 

💡 구현 아이디어

---

이 문제의 포인트는 닫는 괄호가 레이저인지 쇠막대기의 끝인지를 구분하는 것이다. 

( ) 이렇게 나오면 레이저이고,

) ) 이처럼 닫는 괄호가 연속해서 나올 때 이때 두 번째 괄호는 쇠막대기의 끝이 된다.

 

조각은 1) 레이저에 의해 생기는 경우와 2) 쇠막대기의 끝이어서 생기는 경우 두 가지 경우로 생긴다. 

 

1) 레이저에 의해 조각이 생기는 경우

앞에서 나온 (레이저가 아닌) 여는 괄호 '('의 수 만큼 더해준다. 이때 레이저가 아닌 여는 괄호들은 stack에 하나씩 추가해준다. 따라서 레이저가 나오면 스택의 길이(len(stack))만큼 더해준다.

 

2) 쇠막대기의 끝이어서 조각이 생기는 경우

닫는 괄호가 쇠막대기의 끝이라면, +1만 해주면 된다. 이때 stack 에서 요소 하나를 pop 해서 제거한다.

 

전체 소스 코드는 다음과 같다.

 

💻 소스 코드

---

str = input()
stack = []
ans = 0

for i in range(len(str)):
    if str[i] == '(': # 여는 괄호
        stack.append('(')
    else: # 닫는 괄호
        stack.pop()
        if i > 0 and str[i-1] == '(': # 레이저인 경우
            ans += len(stack)
        if i > 0 and str[i-1] == ')': # 쇠막대기의 끝인 경우
            ans += 1
print(ans)