(C++) - 백준(BOJ) 4889번 : 안정적인 문자열

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

4889번: 안정적인 문자열

문자열을 다루는 문제였습니다.

 

 

 

📕 풀이방법

 문자열의 길이가 2000이므로 재귀적인 방법으로는 어렵다는 생각을 하게 되었습니다. 

 

 1. 입력을 받고 올바른 문자열들을 한 번 stack을 이용해 걸러줍니다.

 

 2. 걸러진 문자열들 또한 길이가 짝수입니다. '{ }' 를 하나의 세트로 지웠기 때문입니다. 따라서 '{'와 '}'의 개수는 둘 다 짝수이거나 둘 다 홀수인 두 가지 경우뿐입니다. 즉, 홀수 + 홀수 = 짝수, 짝수 + 짝수 = 짝수 입니다. 

 

  2-1. '{' 도 홀수 개, '}' 도 홀수 개인 경우

한 번 올바른 문자열들이 걸러진 뒤의 형태는 " } } } { { { ", " } { { { { { ", " } } } { "등이 있습니다. 최소로 바꾸는 경우는 한 칸씩 건너뛰면서 뒤집어주는 방법입니다. 이렇게 해도 가장 중앙에 '}{' 부분은 무조건 바꿔줘야 합니다. 2번의 횟수를 연속으로 소모할 수 밖에 없습니다.

따라서 ('{'의 개수 / 2 + 1) + ('{'의 개수 / 2 + 1)가 답입니다.

 

 2-2. '{'가 짝수 개, '}'도 짝수개인 경우 : " } } { { ", " } } { { { { ", " } } } } { { " 등이 있습니다. 이 경우에는 1칸씩 건너 바꿔준다면 올바른 문자열로 만들 수 있습니다. 따라서 답은 걸러진 문자열의 길이 / 2 입니다.

 

 

---

📕 Code

#include <bits/stdc++.h>
using namespace std;
using pci = pair<char,int>;
int cnt = 0;
int main(){
    while(1){
        cnt++;
        string s, filtered="";
        int isFiltered[2001] ={0};
        stack <pci> st;
        cin >> s;
        if(s[0] == '-') break;
        for(int i = 0; i < s.size(); i++){
            if(s[i] == '{')
                st.push({s[i],i});
            else {
                if(st.size() && st.top().first == '{'){
                    isFiltered[st.top().second] = 1;
                    isFiltered[i] = 1;
                    st.pop();
                }
            }
        }
        int leftBracket = 0, rightBracket = 0;
        for(int i = 0; i < s.size(); i++){
            if(!isFiltered[i]) {
                filtered += s[i];
                if(s[i] == '{') leftBracket++;
                else rightBracket++;
            }
        }
        if(leftBracket % 2 && rightBracket % 2){
            cout << cnt << ". " << leftBracket / 2 + 1 + rightBracket / 2 + 1 << '\n';
        }
        else{
            cout << cnt << ". " << leftBracket / 2 + rightBracket / 2 << '\n';
        }
    }
}

 

---

📕 Test Case

 몇 가지 반례를 직접 작성해 보았습니다. 

 

input

}{{{{{

답 : 4

 

input

}}}{{{

답 : 4

 

input

}}{{{{

답 : 3

 

input

}{}}{}}{}{}{}{{{}}}}}}{{{{}{}{}{

답 : 5