쇠막대기 자르기

📌 백준 10799번 - 쇠막대기 (스택)

문제는 다음과 같음 👇

- "(" 막대의 시작을 STACK 에 저장하고,
- ")" 를 만날때 레이저이기 때문에 레이저 구성인 '(' 를 스택에서 제거한 뒤
- 나머지 스택의 길이를 z(조각)에 저장합니다. (레이저를 만나서 잘린 조각)
- 이후 ")"의 전 괄호가 ')' 일 경우에는 하나의 막대가 끝난것이기 때문에 +1을 해줍니다
  (끝난 막대의 마지막 잘린 조각 더해줌)

코드

n = "()(((()())(())()))(())"

bar_stack = []
z = 0
for i, _ in enumerate(n):
    if n[i] == "(":
        bar_stack.append(n[i])
    else:
        if n[i-1] == "(":
            bar_stack.pop()
            z += len(bar_stack)  # 레이저로 잘린 조각 수
        elif n[i-1] == ")":
            bar_stack.pop()
            z += 1              # 막대 끝, 조각 +1

print(z)

핵심 포인트

• 레이저는 ()로 표현되고, 스택에 쌓인 모든 막대를 자름 → 잘린 조각 수는 현재 스택의 길이
• 닫는 괄호 ) 앞에 )가 있다면 → 하나의 막대 끝 → 조각 1개 추가

설명

• 레이저는 지나가면서 현재 열려 있는 모든 막대를 자름 → 그 순간 스택에 쌓인 '(' 개수만큼 조각 생김
• 막대가 끝날 때는 마지막 남은 잘린 1조각을  추가함

시간복잡도

O(N) → 괄호를 한 번씩만 순회하면서 스택 사용