https://www.acmicpc.net/problem/4889

문제

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

1. 빈 문자열은 안정적이다.
2. S가 안정적이라면, {S}도 안정적인 문자열이다.
3. S와 T가 안정적이라면, ST(두 문자열의 연결)도 안정적이다.

{}, {}{}, {{}{}}는 안정적인 문자열이지만, }{, {{}{, {}{는 안정적인 문자열이 아니다.

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

입력

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

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

출력

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

예제 입출력

• 예제 입력 1

}{
{}{}{}
{{{}
---

• 예제 출력 1

1. 2
2. 0
3. 1

Solution

#include <bits/stdc++.h>

using namespace std;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    string Str;
    int caseNum = 1;
    while(1){
        cin >> Str;
        if(Str[0] == '-'){
            break;
        }
        int result = 0;
        stack<char> stk;
        for(auto i : Str){
            if(i == '}' && !stk.empty() && stk.top() == '{'){
                stk.pop();
            } else {
                stk.push(i);
            }
        }

        while(!stk.empty()){
            char first = stk.top();
            stk.pop();
            char second = stk.top();
            stk.pop();
            if(first == second) result++;
            else result += 2;
        }
        cout << caseNum << ". " << result << '\n';
        caseNum++;
    }
    return 0;
}

생각보다 참 간단하게 풀리던 문제.
사실 꽤 오래전, 같은 문제를 못 풀었던 경험이 있다.

중요한 로직은 다음과 같다.
1. 일단 가능한 모든 안정적인 문자열들을 날려버린다.
2. 남아있는 문자열들에 대해 최소한의 계산 량을 카운트한다.

첫 번째 로직부터 살펴보자.

cin >> Str;
if(Str[0] == '-'){
    break;
}
int result = 0;
stack<char> stk;
for(auto i : Str){
   if(i == '}' && !stk.empty() && stk.top() == '{'){
        stk.pop();
    } else {
        stk.push(i);
    }
}

우선 입력받은 데이터에 대해 스택을 활용하여 당장 가능한 안정적인 문자열들을 모두 날린다.
단, 그렇다고 해서 매번 데이터 하나하나를 검토하는 과정에서 처음부터 문자열을 뒤질 필요는 없다.
당장 문자열을 순서대로 읽으며, 그 시점에서 당장 안정적인 문자열 하나를 날릴 수 있는지를 확인하는 것이다.

while(!stk.empty()){
    char first = stk.top();
    stk.pop();
    char second = stk.top();
    stk.pop();
    if(first == second) result++;
    else result += 2;
}

그 후 스택에 남아있는 데이터들을 하나하나 꺼내서 안정적인 문자열로 만들어주면 끝.

어떤 순서로 문제를 해결하는 지에 초점을 두어야 했던 문제였다.