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

Peace·2021년 1월 16일

백준

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

문제 링크: https://www.acmicpc.net/problem/4889

문제

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

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

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

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

입력

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

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

출력

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

문제 이해

올바르게 괄호의 짝이 맞도록 구현하는 문제이다. }{가 들어오면 최소 연산 수로 {}로 만드는 것이다.

문제 접근

'{' 가 들어오면 push

'}' 가 들어오면

stack이 empty라면 {로 바꿔서 push 하고 count(바꾼 횟수) + 1 해준다.

empty가 아니라면 pop 해준다.

문자열을 다 체크했을때

stack이 empty가 아니면, stack안에 들어 있는 개수/2 + count를 return

empty라면, count return.

코드 구현(c++)

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int bracketChange(string str){
    vector<char> brackets;
    int count = 0;
    for(int i = 0 ; i < str.length() ; i++){
        if(str[i] == '{') brackets.push_back(str[i]);
        else{
            if(brackets.empty()) {
                brackets.push_back('}');
                count++;
            }
            else brackets.pop_back();
        }
    }
    if(!brackets.empty()) return count + (brackets.size() / 2);
    return count;
}

int main(){
    string str;
    int countNum = 0;
    int changeNum;
    while(1){
        cin >> str;
        if(str[0] == '-') break;
        countNum++;
        changeNum = bracketChange(str);
        cout << countNum << ". " << changeNum << "\n";
    }
}