[BOJ] 4949 - The Balance of the World

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

---

[알고리즘풀이]

()괄호를 위한 스택1과 []괄호를 위한 스택2 두 개를 이용해서 문제를 해결한다.

1. '(' 괄호를 만나면 스택1에 푸쉬한다.

2. ')' 괄호를 만나면 스택1을 팝한다. 이때, 스택1이 비어있다면 '(' 와 짝이 맞지 않으므로 "NO"를

또 스택2의 top이 스택1의 top보다 크다면 "NO"를 출력하고 종료한다. 아니라면, 계속 진행한다.

* 다음과 같은 경우 : ( [ ) ] 를 의미한다. 

3. 진행이 완료되었을 때, 스택1에 남아있는 '('가 있다면 "NO"를 출력, 아니라면 "YES"를 출력한다.

[]괄호도 마찬가지로 1,2,3 과정을 거친다.

 

[주의사항]

( [ ) ] 과 같은 예시도 ( ) 와 [ ] 가 짝이 맞지만, 균형이 무너져 안 되는 점을 주의해야 한다.

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

using namespace std;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
	while(1){
		bool flag = false;
		string input;
		getline(cin, input);
		if (input == ".")
			return 0;
		stack<int> s1, s2;
		for (int i = 0; i < input.length(); i++) {
			if (input[i] == '(') {
				s1.push(i);
			}
			else if (input[i] == '[') {
				s2.push(i);
			}
			else if (input[i] == ')') {
				if (s1.empty()) {
					flag = true;
					break;
				}
				if (s2.empty()) {
					s1.pop();
					continue;
				}
				int c1 = s1.top();
				int c2 = s2.top();
				if (c1 < c2) {
					flag = true;
					break;
				}
				s1.pop();
			}
			else if (input[i] == ']') {
				if (s2.empty()) {
					flag = true;
					break;
				}
				if (s1.empty()) {
					s2.pop();
					continue;
				}
				int c1 = s1.top();
				int c2 = s2.top();
				if (c1 > c2) {
					flag = true;
					break;
				}
				s2.pop();
			}
		}
		 if (flag || !s1.empty() || !s2.empty())
			cout << "no\n";
		else
			cout << "yes\n";
	}
}

---