문제

코드

#include <iostream>
#include <stack>
#include <string>
using namespace std;

// stack: LIFO

// 안정적인 문자열
// {{{{{{ 일 때 {}{}{}이든 {{{}}}이든 3개를 바꿔야 하는 것은 동일

int main() {
  ios::sync_with_stdio(0);

  string s;
  int i=1;

  while(1) {
    stack<char> st;
    cin >> s;

    if(s[0] == '-') { break; }

    int cnt = 0;

    for(int i=0; i<s.size(); i++) {
      if(s[i] == '{') {
        st.push('{');
      } else if(st.empty() && s[i]=='}') {
        st.push('{');
        cnt++;                              // { 로 바꾸어 스택에 넣음. 바꾼 횟수 증가
      } else if(!st.empty() && s[i]=='}') {
        st.pop();                           // 괄호 짝이 맞추어 졌으니 꺼냄
      }
    }

    if(st.size()>0) {
      cnt += st.size()/2;
    }

    cout << i << ". " << cnt << '\n';
    i++;
  }

  return 0;
}

📢

처음엔 왜인지 queue를 이용해 풀려고 했었다. 그래도 stack을 이용해서 풀어야한다는 걸 너무 늦게 알지 않아서 다행이었다.
그림을 그리면서 이해해보니 규칙(?)을 발견할 수 있었다.
처음에는 이렇게 짝수만 된다는걸 생각을 못하고 이런 규칙이 있구나 생각했었는데 생각해보니 짝수만 가능하고 어떤 경우에도 스택에 남아있는('{'가 쌓인 스택) 개수의 절반이 count되면 된다는 것을 알 수 있었다.