BOJ 10799 - 쇠막대기

문제

https://www.acmicpc.net/problem/10799

 

 

풀이

스택을 이용해 문제를 풀 수 있다

 

레이저가 발사되면 스택에 쇠막대기가 쌓인 만큼 조각이 추가된다

 

입력한 문자열을 탐색하면서 다음 과정을 반복한다

 

•  '('를 만나면 스택에 push 한다
•  ')'를 만나면 스택에서 '('를 pop한다. 이때 () 처럼 연속되어서 레이저로 나가는지 확인해야 한다
  • 인덱스 차이가 1이면 레이저로 나간다
  • 그렇지 않으면 막대기의 길이가 끝나는 것이다
• 인덱스 차이가 1이면 스택의 크기만큼 총 개수에 추가한다 (스택의 크기만큼 조각이 생긴다)
• 그렇지 않으면 총 개수에 1을 추가한다 (막대기의 마지막 조각)

 

 

 

코드

python

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