[BOJ/4889] 안정적인 문자열(C++)

문제 링크

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

4889번: 안정적인 문자열

 

풀이

이 문제는 스택 개념을 이용해서 풀 수 있다. 

입력으로 주어진 문자열을 안정적인 문자열로 바꾸는 것인데,

 

주어진 문자열을 하나하나 검사해서

{ 일 경우, 스택에 push 하고

} 인 경우 스택에서 pop을 하면 된다. 

 

다만, 스택이 전부 비어있는 상태에서 }가 들어오면 그 }를 {로 바꿔서 스택에 넣어줘야 한다. 

스택 맨 앞에 있는 } 는 어차피 추후 안정적인 문자열을 만들기 위해 {로 바꿔줘야 하기 때문에, 들어오는 즉시

{로 바꿔서 넣어주는 것이다. 

 

문자열을 스택에 하나씩 넣고 빼는 작업을 마치면, 스택에 남아있는 { 괄호의 개수를 센다. 

안정적인 문자열을 만들기 위해서는 남아있는 { 의 절반은 }로 바꿔야 하므로, { 괄호의 개수에 나누기 2한 값을 연산횟수에 더한다. 

 

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

    int num=1; // 출력을 위한 번호
    int cnt; // 연산횟수
    int left_bracket_cnt; // 스택 안에 들어있는 { 괄호 개수

    int main() {
	string s;
    stack <char> st;

	while(true) {
		getline(cin, s);
		// 문자열에 -가 포함되어 있으면 종료
		if (s.find('-') != string::npos) return 0;
		int len = s.length();
        for (int i=0; i<len; i++) {
            char ch = s[i];
            if (ch == '{') {
                st.push(ch);
            } else if (ch == '}') {
                if (st.empty()) {
                    st.push('{');
                    cnt++; // } -> { 바꿨으므로 연산횟수 증가
                } else if (st.top() == '{') {
                    st.pop();
                }
            }
        }

        while(!st.empty()) {
            char top = st.top();
            if (top == '{') left_bracket_cnt++;
            st.pop();
        }
        cnt += left_bracket_cnt/2;
        cout << num << ". " << cnt << "\n";
      	// 초기화  
        cnt = 0;
        num++;
		left_bracket_cnt = 0;
	}

	return 0;
}