백준 4889

문제

여는 괄호와 닫는 괄호만으로 이루어진 문자열이 주어진다. 여기서 안정적인 문자열을 만들기 위한 최소 연산의 수를 구하려고 한다. 안정적인 문자열의 정의란 다음과 같다.

빈 문자열은 안정적이다.
S가 안정적이라면, {S}도 안정적인 문자열이다.
S와 T가 안정적이라면, ST(두 문자열의 연결)도 안정적이다.
{}, {}{}, {{}{}}는 안정적인 문자열이지만, }{, {{}{, {}{는 안정적인 문자열이 아니다.

문자열에 행할 수 있는 연산은 여는 괄호를 닫는 괄호로 바꾸거나, 닫는 괄호를 여는 괄호로 바꾸는 것 2가지이다.

입력

입력은 여러 개의 데이터 세트로 이루어져 있다. 각 데이터 세트는 한 줄로 이루어져 있다. 줄에는 여는 괄호와 닫는 괄호만으로 이루어진 문자열이 주어진다. 문자열의 길이가 2000을 넘는 경우는 없고, 항상 길이는 짝수이다.

입력의 마지막 줄은 '-'가 한 개 이상 주어진다.

출력

각 테스트 케이스에 대해서, 테스트 케이스 번호와 입력으로 주어진 문자열을 안정적으로 바꾸는데 필요한 최소 연산의 수를 출력한다.

문제 풀이

안정적인 문자열이 아닌 경우에 바꾸는 경우는 두가지가 있다.
1. }{ 와 같이 마주보는 경우 -> 2번
2. }}. {{ 와 같이 같은방향 -> 1번

안정적이지 않은 문자열의 경우, {와 }의 개수만 계산해도 안정적인 문자열로 바꾸는 경우의 수를 구할 수 있다.
}}}{{{, }}}}{{{{와 같은 경우를 예로 들자.
첫번째 경우는 같은 방향이 세쌍식이므로, 결국 마지막에 }{가 남게 된다.
그러므로 }}, {{, }{ 총 4번의 연산이 필요하다.
두번째 경우는 같은 방향이 총 네쌍씩이므로, {{,{{,}},}} 총 4번의 연산으로 끝낼 수 있다.

그러므로 안정적인 문자열을 제외하고, {와 } 각각의 개수를 구한 뒤 이것을 2로 나눈 몫이 1번으로 해결되는 경우고, 만약 나머지가 1이 생길 경우는 +2를 해주면 된다.

정답 코드

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
string s;
int idx=1;
int main(){
    while(cin>>s){
        int ans=0;
        string anss;
        for(auto c : s){
            if(c=='-') return 0;
            if(anss.empty())
                anss.push_back(c);
            else if(anss.back() == '{' && c=='}')
                anss.pop_back();
            else
                anss.push_back(c);
        }
        int c1=0, c2=0;
        for(auto c : anss){
            if(c=='{') c1+=1;
            if(c=='}') c2+=1;
        }
        ans += c1/2;
        ans += c2/2;
        if(c1%2==1)
            ans += 2;
        cout<<idx<<". "<<ans<<'\n';
        idx+=1;
    }
}