boj 4889 c++ 안정적인 문자열

boj 4889 c++ 안정적인 문자열

백준 4889 cpp 안정적인 문자열

 

그리디 + 스택 문제.

짝수 개만 들어오므로, {} 쌍을 모두 지우고 나면 짝수 개의 }} 형태 또는 }{ 만 남는다.

이 때, }} or {{ 의 경우 하나만 뒤집어 주면 되므로 출력할 값에 1을 더하고,

}{ 의 경우 두 개 다 뒤집어 주어야 하므로 출력할 값에 2를 더한다.

또한 출력할 때 그냥 숫자만 출력하는게 아니라 n. answer 의 형식을 띄어야 한다는 것에 유의하자.

 

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

string line;
stack<char> S;

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

    int ansNum = 1; // 출력을 자세히 보면 `1. 정답`의 형태. 
    while (true)
    {
        cin >> line;
        int ans = 0;
        for (int i = 0; i < line.size(); i++)
        {
            char c = line[i];
            if (c == '{')
            {
                S.push(c);
            }
            else if (c == '}')
            {
                if (S.empty() || S.top() != '{')
                {
                    S.push(c);
                }
                else // S.top() == '{'
                {
                    S.pop();
                }
            }
            else // c == '-'
            {
                return 0;
            }
        }
        while (!S.empty())
        {
            char t = S.top();
            S.pop();
            if (S.top() != t)
            {
                ans += 2;
            }
            else // S.top() == t. '{' == '{'
            {
                ans += 1;
            }
            S.pop();
        }
        cout << ansNum++ << ". " << ans << '\n';
    }
}