백준 9012 괄호

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

문제 요약

1. 자료 구조 스택을 이용하여 괄호 검사기를 구현하는 문제
2. VPS(Valid Parenthesis String)인지를 확인하는 과정을 알아야한다.

풀이

1. 가장 기본적으로 스택 자료구조에 대한 이해가 필요하다.
2. VPS(Valid Parenthesis String)인지 확인하기 위해서는 Stack에 하나씩 넣으면서 확인해보아야한다.
3. ( 의 경우 그냥 Stack에 넣어주면 됩니다.
4. ) 의 경우 스택에 해당 괄호의 짝인 (가 이미 스택에 있어야합니다.
   4-1 스택이 비어있다면 VPS가 될 수 없습니다.
   4-2 스택 top에 )가 있다면 VPS가 될 수 없습니다.
   4-3 스택 top에 (가 있다면 VPS가 될 수 있습니다.
5. 모든 문자열을 다 진행한 이후에 stack에 괄호가 남아있다면 VPS가 될 수 없습니다.

코드

string checkBrackets(string t) {
	stack<int> st;
	// ( 는 1로  
	// ) 은 0으로
	bool res = true;
	// true이면 가능한 상태
	// false이면 불가능한 상태

	for (int i = 0; i < t.length(); i++) {
		if (t[i] == '(') {
			st.push(1);
		}
		else if (t[i] == ')') {
			if (st.empty()) {
				res = false;
				break;
			}
			else {
				if (st.top() == ')') {
					res = false;
					break;
				}
				else {
					st.pop();
				}
			}
		}
	}
	
	if (!st.empty()) {
		res = false;
	}

	return res ? "YES": "NO";
}

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

	int T;
	cin >> T;

	string t;
	while (T--) {
		cin >> t;

		cout << checkBrackets(t) << '\n';
	}

	return 0;
}