백준 10799 문제 링크

💡 1. 문제 정의

이 문제는 여는 괄호( '(' )와 닫는 괄호( ')' )로 구성된 입력을 보고 레이저 또는 막대기로 판단해 얻을 수 있는 총 막대기의 개수를 구하는 문제이다.

🤔 2. 해결 방법

스택이란?
스택(stack)을 활용하여 현재까지 잘린(or 안 잘린) 막대기의 개수를 판단하는 것에 활용하도록 한다.

📑 3. 문제 풀이

1. 초기값으로 스택에 '('를 하나 넣는다.
2. 입력 문자열의 2번째부터 하나씩 살펴본다.
3. 현재 문자가 '('라면 스택에 append 한다.
4. 현재 문자가 ')'이고, 바로 이전 문자가 '('였다면 이것은 레이저이다. 따라서 이전 단계에서 '('로 인해 스택에 넣어주었던 값을 하나 pop 해준다. 또한 레이저가 지나가므로 현재까지 파악된 막대기의 앞부분은 잘릴 것이다. 따라서 스택의 길이만큼의 막대기가 생긴다.
5. 현재 문자가 ')'이고, 바로 이전 문자도 ')'였다면 이것은 막대기의 끝이다. 따라서 스택에 넣어주었던 값을 하나 pop 해준다. 또한 레이저가 지나갔든 안 지나갔든 잘린(or 안 잘린) 막대기는 하나 더 생겼다고 볼 수 있다.

bar = input()

stack = ['(']
cnt = 0
for b in range(1, len(bar)):
    if bar[b] == '(':
        # 현재 괄호가 '('라면 쇠막대의 시작이거나 레이저의 시작이다.
        stack.append('(')
    else:
        if bar[b - 1] == '(':
            # 현재 괄호가 ')'이고 이전 괄호가 '('이라면 레이저이다.
            stack.pop()
            cnt += len(stack)
        else:
            # 현재 괄호가 ')'이고 이전 괄호가 ')'이라면 쇠막대의 끝이다.
            stack.pop()
            cnt += 1

print(cnt)