[백준 10799] 쇠막대기 - C++

문제 접근

이 문제는 처음에, 막대 끝이 나왔을 때 지금까지 나온 레이저의 개수를 카운트 하려고 했었다. 하지만 막대의 처음을 파악하기 힘들다는 문제점이 있어서 관점을 바꾸었다.

레이저를 기준으로 관찰해보면, 레이저가 나왔을때 지금까지 쌓인 막대의 개수를 카운팅 하면 쉽게 문제를 풀 수 있다는 걸 알 수 있다. 레이저가 자르는 막대의 수를 파악할 수 있기 때문이다. 레이저가 나오면, 레이저가 자른 왼쪽 토막수를 세고, 막대의 마지막이 나오면 1을 더해줘서 오른쪽에 있는 토막 수도 세주면 된다. 

 

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

void solve() {
  string str;
  cin >> str;

  int ans = 0;
  stack<char> s;
  for(int i = 0; i < str.size(); i ++) {
    if(str[i] == '(') {
      s.push(str[i]);
    } else {
      if(str[i-1] == '(') { // 레이저인 경우
        s.pop();
        ans += s.size();
      } else { // 막대기 끝인 경우
        ans ++;
        s.pop();
      }
    }
  }
  cout << ans;
}

// ************************************

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  solve();
}