(백준 9012번 스택) 라이님 블로그 대회 알고리즘 따라잡기 15) Stack

백준 9012번

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

 

'('의 쌍은 ')'임을 기억해주자!

1. '('가 들어오면 stack에 넣는다

2. ')'가 들어오면 stack에 '('가 있는지 확인한다

- 있으면 '('을 pop해준다

- 없으면 "NO"

3. 1, 2번을 반복한다. 모두 반복한 후 stack이 empty가 아니면 "NO"

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

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int N; cin >> N;
	
	while (N--) {
		stack<char> st;
		string s; cin >> s;
		bool flag = true;
		for (unsigned int i = 0; i < s.size(); i++) {
			//cout << "s[i] : " << s[i] << endl;
			if (s[i] == '(') st.push('(');
			else if (s[i] == ')' && !st.empty()) st.pop();
			else if (s[i] == ')' && st.empty()){ 
				flag = false; 
				break; 
			}
		}
		if (flag && st.empty()) cout << "YES\n";
		else cout << "NO\n";
	}
	return 0;
}