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

백준

 

---

🤔문제 이해

괄호의 짝을 맞추기 위해 최소한으로 바꾸는 괄호의 개수를 구하는 문제이다. 

---

🔥풀이🔥

짝이 맞는 괄호는 stack을 이용해 여는 괄호면 넣고 닫는 괄호면 stack의 top이 여는 괄호면 pop을 해주고, 닫는 괄호면 그냥 push해주는 식으로 처리해주었다.

 

바로 짝을 지어주나 나중에 짝을 지어주나 바꾸는 괄호의 개수는 변하지 않는다.

예를 들어 앞서 든 예시 }{{{의 경우 첫번째와 두번째, 네번째를 바꿔 {}{}을 만드는 것과

첫번째 세번째 네번째를 바꿔 {{}}을 만드는 경우에서 바꾸는 괄호의 개수가 동일함을 알 수 있다.

 

따라서 그리디 알고리즘을 사용해 처음 괄호는 무조건 여는 괄호로 만들어주고, 다음 괄호는 닫는 괄호로 만들어 주면서 문자 2개씩 처리해주었다. 

---

#include <iostream>
#include <stack>
#include <vector>

using namespace std;

string s;

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

    int idx = 1;
    while (true) {
        cin >> s;
        stack<char> st;
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == '{') {
                st.push('{');
            } else if (s[i] == '}') {
                if (!st.empty() && st.top() == '{') {
                    st.pop();
                } else {
                    st.push('}');
                }
            } else {
                return 0;
            }
        }
        vector<char> v;
        while (!st.empty()) {
            v.push_back(st.top());
            st.pop();
        }
        int ans = 0;
        for (int i = v.size() - 1; i >= 0; i--) {
            if (v[i] == '}') {
                ans++;
                i--;
                if (v[i] == '{')
                    ans++;
            } else if (v[i] == '{') {
                i--;
                if (v[i] == '{')
                    ans++;
            }
        }
        cout << idx << ". " << ans << "\n";
        idx++;
    }

}