[BOJ] 4949 - The Balance of the World

안녕하세요.

여행벌입니다.

오늘은 BOJ 4949번 문제를 다뤄보겠습니다.

---

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

4949번: 균형잡힌 세상

[알고리즘]

1. getline 함수를 통해 입력을 받는다.

2. 입력받은 문자열을 앞부터 순회하며 자료구조 Stack을 이용해서 '(' , '[' 을 만나면 Stack에 push 그와 짝인 ')' , ']' 을 만나면 Stack에 pop을 진행한다. 이때, ')', ']' 와 짝인 애들이 없다면(Stack이 비어있다면) 잘못된 문자열이고, 또 '(' 와 ')' 사이에 '[' 가 들어가있거나, '[' 와 ']' 사이에 '(' 에 들어가있어도 잘못된 문자열이다. 마지막으로 순회가 끝나고, Stack에 '(' 와 '[' 가 남아있다면 잘못된 문자열이다.

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

using namespace std;

int main(void) {
	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";
	}
}

---