백준/4949/stack/균형잡힌 세상

백준/4949/stack/균형잡힌 세상
stack를 활용한 문제

간단하게 여는 괄호가 들어오면 stack에 쌓고 닫는 괄호가 나오면 stack에 쌓인 가장 최근 요소를 가져와 닫는 괄호와 짝이 되는 경우에는 통과하고 아니면 break 후 result를 no로 바꾸고 그 result를 vector에 모아서 출력하였다.

그러나 입력 받는 도중 오류가 발생하였다.

A rope may form )( a trail in a maze.

이 문장에서 dequeue 오류가 났다.
이유는 stack에 쌓인 요소가 없는데 닫는 괄호를 보면

else if (a[i] == ')' || a[i] == ']') {
				tmp = open_bracket.top(); open_bracket.pop();
				if (a[i] == ')') {
					if (tmp != '(') {
						result = "no";
						while (!open_bracket.empty()) {
							open_bracket.pop();
						}
						break;
					}
				}
				else {
					if (tmp != '[') {
						result = "no";
						while (!open_bracket.empty()) {
							open_bracket.pop();
						}
						break;
					}
				}
			}

위와 같이 stack에서 요소를 뽑아오게 만들어 오류를 발생시킨것이었다.

			else if (a[i] == ')' || a[i] == ']') {
				if(open_bracket.empty()){
    				result="no"
        			break;
    			}
				tmp = open_bracket.top(); open_bracket.pop();
				if (a[i] == ')') {
					if (tmp != '(') {
						result = "no";
						while (!open_bracket.empty()) {
							open_bracket.pop();
						}
						break;
					}
				}
				else {
					if (tmp != '[') {
						result = "no";
						while (!open_bracket.empty()) {
							open_bracket.pop();
						}
						break;
					}
				}
			}

위와 같이 stack에 쌓인 요소가 없는 상태에서 닫는 괄호를 만나면 result="no"를 내보내고 반복문을 종료시켰다.

그럼에도 불구하고 20%에서 실패하여 반례를 찾다보니

([])[.

입력을 받으면 no를 출력해야 하는데 yes를 출력하여 이유를 보니 여는 괄호를 만난 뒤 닫는 괄호를 만나 다르다는 걸 검사하지 않으면 그냥 넘어가는 것이다.
즉, stack이 비어있는지를 검사하지 않아 발생한 문제이다.

if (!open_bracket.empty()) {
			result = "no";
			while (!open_bracket.empty()) {
				open_bracket.pop();
			}
		}

그래서 for문을 통과하고도 stack에 잔존 요소가 있으면 result를 no로 바꾸고 stack를 비우게 만들었다.

풀이

1. 첫번째 풀이

#include<iostream>
#include<string>
#include<stack>
#include<vector>
using namespace std;
vector<string> h;
stack<char> open_bracket;
int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	string a;
	char tmp;
	string result;

	while (1) {
		getline(cin, a);
		if (a[0] == '.')
			break;
		result = "yes";
		for (int i = 0; a[i] != '.'; i++) {
			if (a[i] == '(' || a[i] == '[') {
				open_bracket.push(a[i]);
			}
			else if (a[i] == ')' || a[i] == ']') {
				tmp = open_bracket.top(); open_bracket.pop();
				if (a[i] == ')') {
					if (tmp != '(') {
						result = "no";
						while (!open_bracket.empty()) {
							open_bracket.pop();
						}
						break;
					}
				}
				else {
					if (tmp != '[') {
						result = "no";
						while (!open_bracket.empty()) {
							open_bracket.pop();
						}
						break;
					}
				}
			}
		}
		h.push_back(result);
	}

	for (auto x : h)
		cout << x << '\n';

}

2. 두번째 풀이

#include<iostream>
#include<string>
#include<stack>
#include<vector>
using namespace std;
vector<string> h;
stack<char> open_bracket;
int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	string a;
	char tmp;
	string result;

	while (1) {
		getline(cin, a);
		if (a[0] == '.')
			break;
		result = "yes";
		for (int i = 0; a[i] != '.'; i++) {
			if (a[i] == '(' || a[i] == '[') {
				open_bracket.push(a[i]);
			}
			else if (a[i] == ')' || a[i] == ']') {
				if (open_bracket.empty()) {
					result = "no";
					break;
				}
				tmp = open_bracket.top(); open_bracket.pop();
				if (a[i] == ')') {
					if (tmp != '(') {
						result = "no";
						while (!open_bracket.empty()) {
							open_bracket.pop();
						}
						break;
					}
				}
				else {
					if (tmp != '[') {
						result = "no";
						while (!open_bracket.empty()) {
							open_bracket.pop();
						}
						break;
					}
				}
			}
		}
		h.push_back(result);
	}

	for (auto x : h)
		cout << x << '\n';

}

3. 세번째 풀이

#include<iostream>
#include<string>
#include<stack>
#include<vector>
using namespace std;
vector<string> h;
stack<char> open_bracket;
int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	string a;
	char tmp;
	string result;

	while (1) {
		getline(cin, a);
		if (a[0] == '.')
			break;
		result = "yes";
		for (int i = 0; a[i] != '.'; i++) {
			if (a[i] == '(' || a[i] == '[') {
				open_bracket.push(a[i]);
			}
			else if (a[i] == ')' || a[i] == ']') {
				if (open_bracket.empty()) {
					result = "no";
					break;
				}
				tmp = open_bracket.top(); open_bracket.pop();
				if (a[i] == ')') {
					if (tmp != '(') {
						result = "no";
						while (!open_bracket.empty()) {
							open_bracket.pop();
						}
						break;
					}
				}
				else {
					if (tmp != '[') {
						result = "no";
						while (!open_bracket.empty()) {
							open_bracket.pop();
						}
						break;
					}
				}
			}
		}
		if (!open_bracket.empty()) {
			result = "no";
			while (!open_bracket.empty()) {
				open_bracket.pop();
			}
		}
		h.push_back(result);
	}

	for (auto x : h)
		cout << x << '\n';

}

4.네번째 풀이(모듈화)

#include<iostream>
#include<stack>
#include<vector>
#include<string>
using namespace std;
string a;
stack<char> S;
vector<string> result;
string result_s;

void remove();
void func();
void solution();

void remove() {
	while (!S.empty())
		S.pop();
}

void func() {
	while (1) {
		result_s = "yes";
		getline(cin, a);
		if (a[0] == '.')
			break;
		for (int i = 0; a[i] != '.'; i++) {
			if (a[i] == '(' || a[i] == '[') {
				S.push(a[i]);
			}
			else if (a[i] == ')' || a[i] == ']') {
				if (S.empty()) {
					remove();
					result_s = "no";
					break;
				}
				char tmp = S.top(); S.pop();
				if (a[i] == ')') {
					if (tmp != '(') {
						remove();
						result_s = "no";
						break;
					}
				}
				else {
					if (tmp != '[') {
						remove();
						result_s = "no";
						break;
					}
				}
			}
		}
		if (!S.empty()) {
			remove();
			result_s = "no";
		}
		result.push_back(result_s);
		remove();
	}
	solution();
}

void solution() {
	for (auto x : result)
		cout << x << '\n';
}

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	func();
}