쇠막대기

백준 10799

잘려진 쇠막대기 조각의 총 개수를 구하기.

• 쇠막대기는 자신보다 긴 쇠막대기 위에만 놓일 수 있다. - 쇠막대기를 다른 쇠막대기 위에 놓는 경우 완전히 포함되도록 놓되, 끝점은 겹치지 않도록 놓는다.
• 각 쇠막대기를 자르는 레이저는 적어도 하나 존재한다.
• 레이저는 어떤 쇠막대기의 양 끝점과도 겹치지 않는다.
• 레이저는 여는 괄호와 닫는 괄호의 인접한 쌍 ‘( ) ’ 으로 표현된다. 또한, 모든 ‘( ) ’는 반드시 레이저를 표현한다.
• 쇠막대기의 왼쪽 끝은 여는 괄호 ‘ ( ’ 로, 오른쪽 끝은 닫힌 괄호 ‘) ’ 로 표현된다.
• 한 줄에 쇠막대기와 레이저의 배치를 나타내는 괄호 표현이 공백없이 주어진다. 괄호 문자의 개수는 최대 100,000이다.

입출력

입력	출력
()(((()())(())()))(())	17
(((()(()()))(())()))(()())	24

---

접근 방식

: 잘려진 막대 수는 해당 막대 ( .... ) 안의 레이저 () 개수 +1 이다. 이들의 합을 구하면 된다.
i번째 원소가 ( 이면 stack에 인덱스를 저장한다.
i번째 원소가 ) 이면 stack에서 pop한다. 이 pop한 원소가 짝을 이루는 원소의 인덱스 이므로, 둘의 인덱스 범위 내의 원소에서 ()개수+1 을 더한다.
-> 시간 초과 발생 ---> 방법을 바꿔야 한다.

알게된 점

• ( 를 만나면 스택에 넣는다.
• ) 를 만났을 때
  • 바로 전 원소가 (이라면 레이저 이므로 pop하고 남은 스택의 길이 만큼을 더해준다.
  • 바로 전 원소가 )이라면 막대 하나의 길이가 끝난 것이므로 +1을 해준다.

코드

import sys

string = sys.stdin.readline().strip()
stack = []
result = 0

for i in range(len(string)):
    if string[i]=='(':
        stack.append(string[i])
    elif string[i]==')':
        if string[i-1] == '(': #레이저
            stack.pop()
            result += len(stack)
        elif string[i-1] == ')':  #쇠막대기 길이 끝
            stack.pop()
            result += 1

print(result)