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

www.acmicpc.net

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

문제

💡

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

빈 문자열은 안정적이다.

S가 안정적이라면, {S}도 안정적인 문자열이다.

S와 T가 안정적이라면, ST(두 문자열의 연결)도 안정적이다.

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

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

시간 제한: 1초

메모리 제한: 128MB

입력

💡

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

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

출력

💡

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

예제 입력	예제 출력
}{ {}{}{} {{{} -—	1. 2 2. 0 3. 1

풀이

스택을 사용해서 풀었다.

입력한 문자열을 분석해 ‘{’ 이면 스택에 넣고 ‘}’이면 스택을 뺀다.

스택이 비어있는 경우, count를 한다.

count값과 스택의 크기를 더해주면 되는데, 같은 방향의 중괄호가 짝수이면 하나만 바꿔도 되니 2로 나눠준 값을 더하고, 나머지가 발생하면 1회는 무조건 바꿔야하니 %2 값을 더한다.

코드


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

int solution(string input)
{
    stack<char> str;
    int count = 0;
    for (auto i : input)
    {
        if (i == '{')
        {
            str.push(i);
        }
        else
        {
            if (str.empty())
            {
                count++;                
            }else
            {
                str.pop();
            }
        }
    }
    return count/2 + count%2 + (str.size()/2) + str.size()%2;
}
int main()
{
    string input = "0";
    vector<string> data;
    while (true)
    {
        cin >> input;
        if (input[0] == '-') break;
        data.push_back(input);
    }

    for (int i = 0; i < data.size(); i++)
    {
        cout << i+1 << ". " << solution(data[i]) << "\n";
    }
}