[백준 10799] 쇠막대기 (C#, C++) - soo:bak

문제 링크

10799번 - 쇠막대기

설명

쇠막대기와 레이저가 괄호로 표현될 때, 레이저에 의해 잘린 쇠막대기 조각의 총 개수를 구하는 문제입니다.

접근법

괄호 문자열에서 여는 괄호는 막대의 시작을, 닫는 괄호는 레이저 또는 막대의 끝을 나타냅니다. 닫는 괄호 바로 앞이 여는 괄호이면 레이저이고, 닫는 괄호이면 막대의 끝입니다.

스택을 사용하여 현재 겹쳐 있는 막대의 개수를 추적합니다. 여는 괄호를 만나면 스택에 넣고, 닫는 괄호를 만나면 스택에서 하나를 뺍니다.

이때 레이저인 경우에는 현재 겹쳐 있는 모든 막대가 잘리므로 스택의 크기만큼 조각이 생깁니다. 막대의 끝인 경우에는 그 막대의 마지막 조각 1개가 추가됩니다.

---

Code

C#

using System;
using System.Collections.Generic;

class Program {
  static void Main() {
    var s = Console.ReadLine()!;
    var st = new Stack<char>();
    var ans = 0;
    st.Push(s[0]);
    for (var i = 1; i < s.Length; i++) {
      if (s[i] == '(') st.Push('(');
      else {
        st.Pop();
        if (s[i - 1] == '(') ans += st.Count;
        else ans += 1;
      }
    }
    Console.WriteLine(ans);
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  string s; cin >> s;
  stack<char> st;
  int ans = 0;
  st.push(s[0]);
  for (int i = 1; i < (int)s.size(); i++) {
    if (s[i] == '(') st.push('(');
    else {
      st.pop();
      if (s[i - 1] == '(') ans += st.size();
      else ans += 1;
    }
  }
  cout << ans << "\n";

  return 0;
}