쇠막대기 — 스택 한 번 순회로 조각 수 계산 (BOJ 10799)

아이디어

• 여는 괄호 (: 스택에 push → 현재 열려 있는 막대 수를 의미.

• 닫는 괄호 ):

  • 직전 문자가 (이면 () → 레이저: 방금 연 (를 pop 하고, 현재 열려 있는 막대 수만큼 조각이 늘어남 → ans += st.size().
  • 아니면 막대의 끝: 해당 막대 하나가 끝났으니 pop 하고 ans += 1.

복잡도

• 한 번만 훑으므로 O(n), 스택 공간 O(n).

코드 (원문)

#include <bits/stdc++.h>
using namespace std;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int ans = 0;
    stack<char> st;
    string str = "";
    getline(cin, str);
    for (int i = 0; i < str.size(); i++) {
        if (str[i] == '(') {
            st.push('(');
        }
        else {
            if (!st.empty() && str[i - 1] == '(') {
                st.pop();
                ans += st.size();
            }
            else if (!st.empty()) {
                st.pop();
                ans++;
            }
        }
    }

    cout << ans;
    
    return 0;
}

메모

• 입력은 괄호 문자열 한 줄. 문제 조건상 처음이 )로 시작하지 않으므로 str[i-1] 접근도 안전.
• 스택에는 “현재 열려 있는 막대”만 유지되도록 관리합니다.