[BOJ] 10799: 쇠막대기

문제: https://www.acmicpc.net/problem/10799

 

 

 

 

#include <bits/stdc++.h>
using namespace std;
string str;
stack<char> st;
int result;

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

  cin >> str;
  for (int i = 0; i < str.length(); i++) {
    if (str[i] == '(')
      st.push('(');
    else {
      st.pop();
      if (str[i - 1] == '(')
        result += st.size();
      else
        result++;
    }
  }
  cout << result << '\n';
}

'(' 는 막대의 시작 또는 레이저다.

'(' 를 push하지 않으면 진행이 안 되므로 무조건 스택에 push한다.

 

')' 는 레이저 또는 막대의 끝이다.

')' 을 만나면 무조건 pop 해야하는데, 레이저인지 막대의 끝인지에 따라 처리 방법이 달라진다.

 

')'가 막대의 끝인지 레이저인지는 str[i-1]을 확인하면 알 수 있다.

str[i-1]이 ')' 라면 막대의 끝이라는 의미이고, '(' 라면 레이저라는 의미다.

 

레이저라면 '(' 또한 레이저이므로 pop하고, 스택에 남아 있는 괄호의 개수를 result에 더한다.

=> 이유는 레이저로 인해 현재 스택에 남아 있는 막대의 개수만큼 왼쪽에 조각이 생기기 때문

 

막대의 끝이라면 이후부터는 레이저로 막대를 쪼갤 수 없기 때문에 '(' 를 pop하고,

막대의 마지막 조각을 카운트하기 위해 result에 1을 더한다.

=> 가장 오른쪽에 있는 조각