https://www.acmicpc.net/problem/10799
10799번: 쇠막대기
여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저
www.acmicpc.net
스택을 이용해서 열린 괄호가 나타나면 스택에 추가하고,
닫힌 괄호가 나타나면 그 전의 괄호가 ( 인 경우에는 스택에서 하나를 pop 한 후에 스택의 길이 즉, 지금까지 있는 쇠막대기의 개수만큼 더해준다. 그 전의 괄호가 ( 가 아닌 경우에는 쇠막대기가 끝나는 것이므로 하나를 더해주고 스택에서 하나를 pop한다.
import sys
input = sys.stdin.readline
s = list(input().rstrip())
st = []
ans = 0
for i in range (len(s)):
if (s[i] == '('):
st.append(i)
else:
if (s[i-1] == '('):
st.pop()
ans += len(st)
else:
ans += 1
st.pop()
print(ans)
'알고리즘💻 > 스택&큐&덱' 카테고리의 다른 글
BOJ 5430번: AC (0) | 2021.07.26 |
---|---|
BOJ 20301번: 반전 요세푸스 (0) | 2021.07.25 |
BOJ 2812번: 크게 만들기 (0) | 2021.07.24 |
BOJ 9012번: 괄호 (0) | 2021.07.24 |
BOJ 20923번: 숫자 할리갈리 게임 (0) | 2021.07.23 |