[백준 4889] 안정적인 문자열

www.acmicpc.net/problem/4889

4889번: 안정적인 문자열

 

스택을 사용한다.

{는 무조건 푸쉬한다.

}의 경우 이전에 {가 있으면 팝을 한다. => 이 경우 안정적인 문자열이다.

이전에 {가 없을 경우 문제가 발생한다. ('}'을 푸쉬하는 일은 없으므로 stack은 empty인 상태일 것이다.)

이 때 }  -> {로 바꿔서 넣어주고 cnt++ 해준다.

 

문자열을 전부 돌고 난 후 스택에 남은 것은 제대로 처리되지 못한 { 일 것이다.

따라서 {을 처리하기 위해 스택 size에 반을 }로 바꾼다.

#include <stack>
#include <stdio.h>
#include <string.h>

using namespace std;
char str[2001];
int main(void)
{
  int t = 0;
  while (1)
  {
    t++;
    scanf("%s", str);
    if (str[0] == '-')
    {
      break;
    }
    int cnt = 0;
    stack<char> s;

    for (int i = 0; i < strlen(str); i++)
    {
      char c = str[i];
      if (c == '{')
      {
        s.push(c);
      }
      else if (c == '}')
      {
        if (s.empty())
        {
          cnt++;
          s.push('{');
        }
        else if (!s.empty() && s.top() == '{')
          s.pop();
      }
    }

    cnt += s.size() / 2;

    printf("%d. %d\n", t, cnt);
  }
  return 0;
}