[BOJ] 11899번 괄호 끼워넣기 (C++)

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

11899번: 괄호 끼워넣기

 

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

int main() {
	stack<char> s;
	stack<char> t;
	string str;
	cin >> str;
	
	for(int i = 0; i < str.length(); i++){
		char c = str[i];
		
		if(c == '('){
			s.push(str[i]);
		} else {
			if(!s.empty()) s.pop();
			else t.push(str[i]);
		}
	}
	
	cout << s.size() + t.size() << endl;
	
	return 0;
}

여는 괄호일 때

s에 push

닫는 괄호일 때

스택 내부에 여는 괄호가 있을 때 -> s pop

없다 -> t에 push

 

s와 t에 push된 괄호는 쌍이 되는 괄호를 붙여주어야 한다.

따라서 앞과 뒤에 붙여야 할 괄호의 최소 개수는 s와 t의 size 합이다.