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

www.acmicpc.net/problem/4889

4889번: 안정적인 문자열

괄호가 입력으로 들어올 때 고려해야 할 경우는 다음과 같습니다.

1. 괄호의 짝이 맞는 경우

2. '}' 가 먼저 들어온 경우 

 

먼저 1번의 경우 괄호 문자열이 입력으로 들어올 때, 짝이 맞는 경우는 전부 제거해줘야 합니다.

그리고 2번의 경우는 스택이 비어있을 때, '}' 가 먼저 들어온 경우 이는 변환이 필요하기 때문에 변환한 수를 증가시키고, 스택에 변환된 괄호의 문자를 넣어줍니다. 

이는 나중에 스택의 길이의 절반 만큼 변환을 해줘야 하기 때문입니다. 예를들어 다음 입력이 들어왔다고 가정합시다.

 

"}{}{{{" 문자열이 들어왔습니다.

'{' 여는 괄호일 때만 스택에 값을 push합니다. 그런데 처음 값이 '}' 입니다. (위의 2번 경우입니다.)

변환한 수 answer값을 1 증가하고, '{'를 스택에 넣어줍니다.

다음에 '{'이 들어가고, 그 후 '}' 를 만나 방금 들어간 '{' 가 pop 됩니다.

그 다음은 전부 '{' 이므로 다 스택에 push 합니다.

현재 스택에 남은 원소는 "{{{{" 가 됩니다.

해당 괄호가 짝이 맞으려면 "{}{}" 이렇게 2번 변환이 필요한데, 이는 현재 스택의 길이의 절반과 같습니다.

따라서 3번 변환해야하므로 answer의 값은 3이 됩니다.

 

#include <iostream>
#include <stack>
using namespace std;

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
    
	int num = 1;
    
	while(1) {
		int answer = 0;
		string str;
		cin >> str;
		if(str.find("-") != string::npos) break; // "-" 이 포함된 문자열 입력시 종료
		stack<char> s;
        
		for(int i = 0; i < str.size(); i++) {
			if(str[i] == '{') {
				s.push(str[i]);
			} else {
				if(!s.empty()) {
					s.pop();
				} else {
					answer++; // 비어있을 때 '}' 이 오는 경우이므로 이는 변환이 필요
					s.push('{'); // 나중에 스택의 길이를 이용해야 하므로 '{'로 변환한 걸 넣어줌
				}
			}
		}
        
		if(s.empty()) { // 안정 상태라면 스택이 비어있음
			cout << num++ << ". " << answer << "\n";
		} else {
			answer += s.size() / 2; // 남아 있는 스택의 절반 변화가 필요
			cout<< num++ << ". " << answer << "\n";
		} 
	}
}