BOJ 4949 - 균형잡힌 세상

균형잡힌 세상 - 🥈 Silver 4

• 문제 링크
  https://www.acmicpc.net/problem/4949

stack을 이용해 풀이할 수 있는 문제이다. 처음에는 스택을 사용하지 않고 문자열을 순서대로 탐색하며 풀이하였다.

괄호를 만났을 때의 경우는 아래와 같이 나눌 수 있다.

• 열린 괄호일 경우
  -> 해당 문자 다음부터 계속 탐색하다 닫힌 괄호를 만나면 끝난 지점 index return
  -> 닫힌 괄호가 없거나 짝이 맞지 않는 경우 -1 return
• 닫힌 괄호일 경우
  -> 현재 탐색중이라면 index return
  -> 탐색중이 아니라면 잘못된 문자열이므로 -1 return

하지만 이러한 방식보다 stack을 사용하여 풀이하는 방식이 간단하여 다시 풀이하였다. 기본적인 방식은 아래와 같다.

• 열린 괄호일 경우
  -> stack에 push
• 닫힌 괄호일 경우
  -> stack이 비었으면 옳지 않은 문자열
  -> stack의 top이 닫힌 괄호와 짝을 이루면 pop 이후 진행
  -> 다를 경우 옳지 않은 문자열
• 끝까지 탐색한 이후
  -> stack이 비어있으면 문제없는 문자열
  -> stack에 남아있는 괄호가 있으면 문제가 있는 문자열

풀이 코드

스택을 사용하지 않은 풀이 (비효율적)

#include <iostream>
#include <string>
#include <stack>
using namespace std;

int isBalanced(int size, int currentIndex, char seperator, string text) {
	int result = 1;
	for (int i = currentIndex; i < size; i++) {
		if (text[i] == '(') {
			i = isBalanced(size, i + 1, '(', text);
		}
		else if (text[i] == '[') {
			i = isBalanced(size, i + 1, '[', text);
		}
		else if (text[i] == ')') {
			if (seperator == '(') {
				return i;
			}
			else {
				return -1;
			}
		}
		else if (text[i] == ']') {
			if (seperator == '[') {
				return i;
			}
			else {
				return -1;
			}
		}
		if (i == -1) {
			result = -1;
			return -1;
		}
	}

	if (seperator != 'n'){
		return -1;
	}

	return result;
}

int main() {
	stack<string> storeText;
	stack<string> result;
	string input = "";

	while (true) {
		getline(cin, input);
		if (input == ".") {
			break;
		}
		storeText.push(input);
	}

	while (!storeText.empty()) {
		int n;
		n = isBalanced(storeText.top().length(), 0, 'n', storeText.top());
		if (n == 1) {
			result.push("yes");
		}
		else {
			result.push("no");
		}
		storeText.pop();
	}

	while (!result.empty()) {
		cout << result.top() << endl;
		result.pop();
	}
}

스택을 사용한 풀이

#include <iostream>
#include <string>
#include <stack>
using namespace std;

int isBalanced(string text) {
	stack<char> s;
	for (int i = 0; i < text.length(); i++) {
		if (text[i] == '(' || text[i] == '[') {
			s.push(text[i]);
		}
		if (text[i] == ')') {
			if (s.empty() || s.top() == '[') {
				return -1;
			}
			else if (s.top() == '(') {
				s.pop();
			}
		}
		if (text[i] == ']') {
			if (s.empty() || s.top() == '(') {
				return -1;
			}
			else if (s.top() == '[') {
				s.pop();
			}
		}
	}

	if (s.empty()) {
		return 1;
	}
	else {
		return -1;
	}
}

int main() {
	stack<string> storeText;
	stack<string> result;
	string input = "";

	while (true) {
		getline(cin, input);
		if (input == ".") {
			break;
		}
		storeText.push(input);
	}

	while (!storeText.empty()) {
		int n;
		n = isBalanced(storeText.top());
		if (n == 1) {
			result.push("yes");
		}
		else {
			result.push("no");
		}
		storeText.pop();
	}

	while (!result.empty()) {
		cout << result.top() << endl;
		result.pop();
	}
}

결과

상단이 stack을 이용한 풀이 결과, 하단이 첫 방식의 결과이다.