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

문제: www.acmicpc.net/problem/4889

4889번: 안정적인 문자열

 

 

문제풀이

 

스택을 이용한 괄호 쌍 맞추기 문제이다.

 

괄호 쌍이 맞지 않게 입력이 되었다면 '{'을 '}'으로 또는 '}'를 '{'으로 바꿔 짝을 맞추는 최소 연산 횟수를 구한다.

 

} -> {      :     '}'이 입력되었을 때 스택이 비어있다면 실행

 

{ -> }      :     입력 종료 후 스택에 남아있는 '{'에 대하여 실행(괄호 짝수개가 입력되므로 스택 사이즈의 2분의 1)

 

 

코드

#include <iostream>
#include <stack>

using namespace std;

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


    int cnt, testCase = 0;
    string str;
    stack<char> s;
    while (true){
        cin>>str;
        cnt = 0;
        testCase++;

        if(str[0] == '-') //하이픈이 입력되면 루프 종료
            break;

        while(!s.empty()) //다음 테스트케이스를 위해 스택 초기화
            s.pop();

        for(int i=0; i<str.length(); i++){
            if(str[i] == '{'){
                s.push(str[i]);
            }
            else{ //str[i] == '}'
                if(s.empty()){ //스택에 '{'가 없이 '}' 입력되면
                    cnt++; //연산 횟수 증가
                    s.push('{'); //'}'를 '{'으로 바꿨으므로 '{' 푸시
                }
                else{
                    s.pop();
                }
            }
        }

        cnt += s.size()/2; //스택에 짝수 개의 '{'가 남아있을 수 있으므로 스택사이즈/2를 더해줌

        cout<<testCase<<". "<<cnt<<"\n";
    }

    return 0;
}

 

 

결과