C++ 백준 4949번

백준 4949번 www.acmicpc.net/problem/4949

4949번: 균형잡힌 세상

문제 : 세계는 균형이 잘 잡혀있어야 한다. 양과 음, 빛과 어둠 그리고 왼쪽 괄호와 오른쪽 괄호처럼 말이다.

정민이의 임무는 어떤 문자열이 주어졌을 때, 괄호들의 균형이 잘 맞춰져 있는지 판단하는 프로그램을 짜는 것이다.

문자열에 포함되는 괄호는 소괄호("()")와 대괄호("[]")로 2종류이고, 문자열이 균형을 이루는 조건은 아래와 같다.

• 모든 왼쪽 소괄호("(")는 오른쪽 소괄호(")")와만 짝을 이뤄야 한다.
• 모든 왼쪽 대괄호("[")는 오른쪽 대괄호("]")와만 짝을 이뤄야 한다.
• 모든 오른쪽 괄호들은 자신과 짝을 이룰 수 있는 왼쪽 괄호가 존재한다.
• 모든 괄호들의 짝은 1:1 매칭만 가능하다. 즉, 괄호 하나가 둘 이상의 괄호와 짝지어지지 않는다.
• 짝을 이루는 두 괄호가 있을 때, 그 사이에 있는 문자열도 균형이 잡혀야 한다.

정민이를 도와 문자열이 주어졌을 때 균형잡힌 문자열인지 아닌지를 판단해보자.

 

여는 괄호( [ , ( )를 만나면 얘네를 스택에 저장하고 닫는 괄호를 만나면 스택에 저장된 여는 괄호가 있는지, 이 닫는 괄호가 여는 괄호랑 일치하는지(대괄호면 대괄호랑, 소괄호면 소괄호랑) 검사하고 일치하는 괄호면 스택에 들어있는 여는 괄호 하나를 pop 해준다. 여는 괄호가 없거나 일치하지 않는 괄호면 올바른 문자열이 아니므로 false를 정답에 저장해준다.

그리고 마지막에 스택에 모두 다 비어야 올바른 문자열이므로 한번 검사해주면 된다!! (닫는괄호와 여는 괄호의 개수가 똑같으면 스택이 다 비게 되겠지!!)

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

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	while (1) {
		string str;
		getline(cin, str); // 한 줄씩
		stack<char>s; // 괄호 저장
		bool ans = true; // yes 인지 no인지!!
		if (str.length() == 1 && str[0] == '.') break;
		for (int i = 0; i < str.length(); i++) {
			if (str[i] == '(' || str[i] == '[') {
				s.push(str[i]);
			}
			if (str[i] == ')') {
				if (s.empty() || s.top() == '[') ans = false;
				else s.pop();
			}
			if (str[i] == ']') {
				if (s.empty() || s.top() == '(') ans = false;
				else s.pop();
			}
		}
		if (s.empty() && ans) cout << "yes" << '\n'; // 모든 과정이 끝났을때 stack 비어있고 ans가 true면 문자열이 균형
		else cout << "no" << '\n';
	}
	return 0;
}