[BOJ] 9012 - Parenthesis

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

---

[알고리즘풀이]

자료 구조 책 스택 단원에 소개될 만큼 대표적인 스택을 사용하는 문제다.

'(' 를 Input으로 받으면 스택에 Push하고, ')' 를 Input으로 받으면 반대로 스택을 Pop한다.

이때, 스택이 비어있어 Pop을 진행하지 못하거나, 모든 Input이 끝나고 짝이 맞지 않아 스택에 '(' 이 남아있다면

"NO"를 출력하고 위의 두 가지 경우가 아니라면 "YES"를 출력한다.

#include<iostream>
#include<stack>
#include<string>

using namespace std;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);

	int ninput;
	cin >> ninput;
	for (int i = 0; i < ninput; i++) {
		stack<int> list;
		string input;
		cin >> input;
		int flag = 0;
		for (int j = 0; j < input.length(); j++) {
			if (input[j] == '(')
				list.push(j);
			if (input[j] == ')') {
				if (list.empty()) {
					cout << "NO\n";
					flag = 1;
					break;
				}
				else
					list.pop();
			}
		}
		if (list.empty() && flag == 0)
			cout << "YES\n";
		else if (!list.empty() && flag == 0)
			cout << "NO\n";
	}
}

---