[백준] 10799번 쇠막대기

아이디어

언제 조각이 생기는가?

1) 레이저를 지나갈때  >> 끝점이 아닌 막대기의 수만큼의 조각이 생긴다  (이건 스택에 들어있는개수로 구하면 됨)

2) 막대기의 끝점일때  >> 끝점인 막대기 조각만 1개 생긴다.

 

위 2가지 경우를 기준으로 나눠 조각을 카운트해준다.

주의할 점은 닫힌 괄호가 나왔을 때, 막대기의 끝점인지, 레이저인지 판단할 필요가 있다.

 

해결

import sys
from collections import deque
input = sys.stdin.readline

queue = deque()
string = input().rstrip()
cnt=0

for i in range(len(string)):
    if string[i]==')':
        if string[i-1]==")":    #레이저가 아니고 한 막대기의 끝점이면
            cnt+=1              #그 막대기 조각만 하나 더 생김
            queue.pop()   
        else:                   #레이저면
            queue.pop()
            cnt+=len(queue)     #스택에 남아있는 개수만큼 조각이 생김
    else:                       #열린괄호면 스택에 추가
        queue.append(string[i])
print(cnt)