백준 4889, 안정적인 문자열

개요

문제 링크
실버 1, Greedy
{안정}, 안정,안정 등의 안정된 괄호 문자열로 변환하기 위한 최소 변환수

---

접근

1. 그리디한 인간이 되어보자. 만약 { 로만 이루어진 문자열이 있다면 n/2번만 바꿔주면 된다.

   {{{{ -> {{}} 4/2 = 2회
   {{{{{{ -> {{{}}} 6/2 = 3회
   {{{{{}{{ -> {{}}{}{} (4+2)/2 = 3회

   홀수개가 나오면 어떻게 하나요? 문제에 짝수라고 주어짐

2. 그럼 } 이 더 많이 나올 때만 { 로 바꿔주고, { 의 연속개수의 합을 구해주면 끝 아닌가?

3. } 이 { 보다 더 많이 나오는 것은 어떻게 판단하냐? 하면 { 이 나올때 +1, } 이 나올 때 -1 해주면 됨. 만약 } 를 마주쳤는데 값이 음수다? 그러면 앞까지 } 이 더 많이 나온 것

4. 이 괄호 문제는 항상 단순하게 풀리고 항상 까먹는다. 그리디의 얍삽함을 항상 탑재한 인간이 되어야 언제든 봐도 풀 수 있음.

---

Pseudo code

for (x = 문자열)
    if (x = "{")
        cnt++
    if (x = "}" 이면서 더 많이 나온경우 = cnt <= 0)
        change++, cnt++
        // } 를 { 로 바꿨으니 cnt++
    else if (x = "}")
        cnt--

// 여기까지 하고 남은 cnt = "{"의 연속개수의 합
// 따라서 최소 변경 = change + cnt / 2

---

Source code

#include <bits/stdc++.h>
using namespace std;

string s;
int test(string s) {
    int cnt = 0;
    int chan = 0;
    for (int i=0; i<s.size(); i++)
        if (s[i] == '{')
            cnt++;
        else if (cnt <= 0)
            chan++, cnt++;
        else
            cnt--;
    return chan+cnt/2;
}

int main() {
    for (int t=1;;t++) {
        cin >> s;
        if (s[0] == '-')
            break;
        cout << t << ". " << test(s) <<"\n";
    }
}