[백준][10799] 쇠막대기

• Problem Link : https://www.acmicpc.net/problem/문제번호

문제

• 레이저는 '()'로 표현 쇠막대의 왼쪽 끝은 '(', 오른쪽 끝은 ')'
• 레이저가 쇠막대기를 절단한다고 한다.
• 쇠막대기와 레이저의 배치를 나타내는 괄호 표현이 주어졌을 때, 잘려진 쇠막대기 조각의 총 개수를 구하여라.

입력

• 첫째 줄, 쇠막대기와 레이저의 배치를 나타내는 괄호 표현이 주어진다.

출력

• 잘려진 조각의 총 개수를 출력한다.

풀이

이 그림을 보고 스택이 떠올라야한다. '('가 들어오면 쇠막대기가 들어왔다는 것을 의미하고 ')'는 쇠막대기 빠졌다는 것을 의미한다. '()'가 들어오면 레이저가 들어왔다는 것이다.

• '('는 따라서 스택에 push를 해준다.
• ')'는 스택에서 pop을 해준다.
  이 때 중요한 점은 레이저를 구분해야한다는 점이다.
  - 따라서 ')'이면 그 앞의 원소가 '('이면 레이저 처리
  - 앞의 원소가 ')'이면 레이저가 아니라 그냥 쇠막대를 빼는 처리
  

그렇다면 쇠막대 조각을 언제 개수를 늘려줘야할까?

• 1. 레이저를 만났을때?
     스택에 남아있는 쇠막대기 개수만큼 늘려준다.
     위 그림을 참고해보자 레이저로 자르면 기존의 스택에 쌓여있던 쇠막대기 3개가 잘리면서 조각이 3개가 늘어났다.
• 2. 레이저가 아니라 그냥 쇠막대기를 뺐을때?
     그냥 맨 위에 있는 쇠막대기 조각을 빼는 것이기 때문에 1개만 늘려준 후 pop을 해준다.

즉, 이 문제의 관건은 첫번째로 스택이라는 자료 구조를 사용할 생각이 문제를 읽자마자 드는가와 ')'를 만났을때 레이저로 처리할 것인지, 아니면 그냥 쇠막대기를 빼는 것인지 이 두 가지를 구별해서 처리할 수 있는가를 주로 물어보는 문제이다.

코드

import sys
from collections import deque

input = sys.stdin.readline

s = input().strip()

ans = 0


q = deque()
for i in range(len(s)):
    if s[i] == "(":
        q.append(s[i])
    if s[i] == ")":
        if s[i - 1] == "(":  # 레이저
            q.pop()
            ans += len(q)
        else:
            q.pop()
            ans += 1

print(ans)