[BOJ] 4949 - The Balance of the World 코드 개선

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

기존풀이 : https://travelbeeee.tistory.com/73

---

[알고리즘풀이]

기존에는 괄호 종류에 따라 stack을 2개 선언해주고 ( [ ) ] 같이 잘못 짝꿍이 맞는 경우에 대해서

Index를 이용해서 검사를 해줬습니다.

하지만, stack을 하나만 선언하고 괄호 2가지 종류를 같은 stack에 Push 하면서 짝궁이 맞지 않는 경우나 짝궁이 없는 경우를 한 번에 검사할 수 있습니다. 따라서 If문으로 나누어 검사해야 되는 경우가 줄어들어 훨씬 편리합니다.

 

-Stack을 2개 이용한 기존 코드

#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";
	}
}

-Stack 하나만을 이용한 개선된 코드

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

using namespace std;

int main(void) {
	while (1) {
		bool flag = false;
		string input;
		getline(cin, input);
		if (input == ".")
			return 0;
		stack<char> c;
		for (int i = 0; i < input.size(); i++) {
			if (input[i] == '(' || input[i] == '[')
				c.push(input[i]);
			else if (input[i] == ')') {
				if (c.empty() || c.top() != '(') { // 짝꿍이 없거나 잘못된 짝꿍
					flag = true;
					break;
				}
				else
					c.pop();
			}
			else if (input[i] == ']') {
				if (c.empty() || c.top() != '[') { // 짝꿍이 없거나 잘못된 짝꿍
					flag = true;
					break;
				}
				else
					c.pop();
			}
		}
		if (flag || !c.empty()) {
			cout << "no\n";
		}
		else
			cout << "yes\n";
	}
}

---