백준 알고리즘 4949번: 균형잡힌 세상 [C++]

문제 출처: www.acmicpc.net/problem/4949

4949번: 균형잡힌 세상

1. 코드

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

int main(void)
{
	while (1)
	{
		string arr;	//원본
		string brr;	//괄호만
		getline(cin, arr, '.');	//'.'이 입력되는 순간까지만 입력
		bool flag = true;		//true라면 yes, false라면 no
		if (arr.empty()) break;	//아무것도 없다면 종료

		for (int i = 0; i < arr.length(); i++)
		{
			if (arr[i] == '(' || arr[i] == '[')		//열린 괄호는 전부 push
				brr.push_back(arr[i]);
			else if (arr[i] == ']')
			{
				if (brr.empty() || brr[brr.length() - 1] != '[')	//비어있거나 열린 대괄호가 아니라면 비교 중지
				{
					flag = false;
					break;
				}
				else brr.pop_back();
			}
			else if (arr[i] == ')')
			{
				if (brr.empty() || brr[brr.length() - 1] != '(')	//비어있거나 열린 소괄호가 아니라면 비교 중지
				{
					flag = false;
					break;
				}
				else brr.pop_back();
			}
		}
		if (flag && brr.empty()) cout << "yes" << endl;		//brr에 괄호가 없고 중간에 정지되지 않았다면 yes
		else cout << "no" << endl;
		cin.ignore();		//입력 버퍼 비워주기
	}
}

(실행)

2. 풀이

string 자료형을 사용하여 열린 괄호일 때는 전부 저장하고 닫힌 괄호가 오면 하나씩 빼주는데 같은 종류의 괄호가 오면 제거해준다. 그리고 열린 괄호보다 닫힌 괄호가 먼저 입력되면 no를 출력해주고 비교가 끝난 뒤 괄호가 남아있다면 no를 출력해주면 된다.

while (1)
{
	string arr;	//원본
	string brr;	//괄호만
	getline(cin, arr, '.');	//'.'이 입력되는 순간까지만 입력
	bool flag = true;		//true라면 yes, false라면 no
	if (arr.empty()) break;	//아무것도 없다면 종료

우선 getlin()을 통해서 '.'이 입력되는 순간까지 입력해준다. '.'만 입력했다면 종료해준다.

for (int i = 0; i < arr.length(); i++)
{
	if (arr[i] == '(' || arr[i] == '[')		//열린 괄호는 전부 push
		brr.push_back(arr[i]);

그리고 입력한 문자열만큼 반복해주는데 괄호를 검사하는 것이다. 그래서 열린 괄호가 있다면 전부 brr에 저장해준다.

else if (arr[i] == ']')
{
	if (brr.empty() || brr[brr.length() - 1] != '[')	//비어있거나 열린 대괄호가 아니라면 비교 중지
	{
		flag = false;
		break;
	}
	else brr.pop_back();
}
else if (arr[i] == ')')
{
	if (brr.empty() || brr[brr.length() - 1] != '(')	//비어있거나 열린 소괄호가 아니라면 비교 중지
	{
		flag = false;
		break;
	}
	else brr.pop_back();
}

각각의 닫힌 괄호가 오면 서로 대칭되는 열린괄호가 이미 저장되어있거나 brr이 비어있지않다면 열린 괄호를 제거해주는데 그렇지않다면 비교하는 반복문을 탈출하고 flag값을 false로 바꾸어준다.

if (flag && brr.empty()) cout << "yes" << endl;		//brr에 괄호가 없고 중간에 정지되지 않았다면 yes
else cout << "no" << endl;
cin.ignore();		//입력 버퍼 비워주기

그리고 brr이 비어있고, flag값이 true라면 yes를 출력 그렇지않다면 no를 출력해주고, 입력버퍼를 비워준다.