[BOJ] 10799. 쇠막대기

📌 문제 제목

문제 링크: BOJ 10799

---

🗒️ 문제 설명

쇠막대기는 여는 괄호와 닫는 괄호로 표현된다.

레이저는 여는 괄호와 닫는 괄호의 인접한 쌍으로 표현된다.

괄호 문자열이 주어졌을 때 잘려진 쇠막대기는 총 몇 개인지 구하는 프로그램.

시간 제한: 1초

메모리 제한: 256MB

---

💡 문제 해결 아이디어

• 여는 괄호 = 스택에 추가
• 닫는 괄호
  • 레이저: 스택의 마지막 원소가 여는 괄호일 경우 레이저임.
    • 스택에 남아있던 여는 괄호들의 개수만큼 쇠막대기가 만들어짐.
    • 스택에 남아있던 여는 괄호들의 갯수를 answer에 추가 (추가: +=)
    • 스택에 남아있던 여는 괄호들의 갯수를 tmp에 추가 (추가: +=)
    • 스택을 비움
  • 쇠막대기: 스택의 마지막 원소가 여는 괄호가 아니면 쇠막대기임.
    
    • answer이 1씩 증가

---

⌛️ 시간 복잡도

• O(N)

---

✅ 최종 코드

import sys
input = sys.stdin.readline

ps = input().strip()

answer = 0
tmp = 0
stk = []

for b in ps:
    if b == "(":
        stk.append(b)
    else:
        if stk and stk[-1] == "(":  # 레이저
            stk.pop()
            answer += (len(stk) + tmp)
            tmp += len(stk)
            stk = []
        else:  # 쇠막대기
            answer += 1
            if tmp:
                tmp -= 1

print(answer)

import sys
input = sys.stdin.readline

ps = input().strip()

answer = 0
stk = []

for i, b in enumerate(ps):
    if b == "(":
        stk.append(b)
    else:
        stk.pop()
        if ps[i-1] == "(":  # 레이저
            answer += len(stk)
        else:  # 쇠막대기
            answer += 1

print(answer)