[백준/C++] 4949번 : 균형잡힌 세상 (문자열 getline, 스택)

균형잡힌 세상

문제

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

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

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

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

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

입력

각 문자열은 마지막 글자를 제외하고 영문 알파벳, 공백, 소괄호("( )"), 대괄호("[ ]")로 이루어져 있으며, 온점(".")으로 끝나고, 길이는 100글자보다 작거나 같다.

입력의 종료조건으로 맨 마지막에 온점 하나(".")가 들어온다.

출력

각 줄마다 해당 문자열이 균형을 이루고 있으면 "yes"를, 아니면 "no"를 출력한다.

예제 입력 1

So when I die (the [first] I will see in (heaven) is a score list).
[ first in ] ( first out ).
Half Moon tonight (At least it is better than no Moon at all].
A rope may form )( a trail in a maze.
Help( I[m being held prisoner in a fortune cookie factory)].
([ (([( [ ] ) ( ) (( ))] )) ]).
 .
.

예제 출력 1

yes
yes
no
no
no
yes
yes

힌트

7번째의 " ."와 같이 괄호가 하나도 없는 경우도 균형잡힌 문자열로 간주할 수 있다.

---

해당 문제는 스택을 이용하여 소괄호 ( ) 와, 대괄호 [ ] 가 순서대로 잘 열고 닫혔는지를 검사하는 문제이다.

 

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

using namespace std;

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	while(true)
	{
		string str;
		getline(cin, str);
		
		if (str == ".") break;

		stack<char> bracket;
		bool No = false;
		for(int i = 0; i < str.length(); i++)
		{
			if (str[i] == '(' || str[i] == '[')
				bracket.push(str[i]);
			else if (str[i] == ')')
			{
				if (!bracket.empty() && bracket.top() == '(')
					bracket.pop();
				else
				{
					No = true;
					break;
				}
			}
			else if(str[i] == ']')
			{
				if(!bracket.empty() && bracket.top() == '[')
					bracket.pop();
				else
				{
					No = true;
					break;
				}
			}
		}
		if (bracket.empty() && !No)
			cout << "yes\n";
		else 
			cout << "no\n";
	}
	return 0;
}

 

📌 문자열 입력 방식

문제를 풀면서 특별히 어려웠던 점은 문자열을 입력받는 형식이었다.

 

처음에는 평소 string을 cin으로 입력받거나 vector<char> 벡터를 cin으로 한 단어씩 입력받는 형태가 익숙해서 그러한 방법으로 문제를 풀었었다.

그러나 char word 변수에 띄어쓰기만을 입력받는 경우에는 띄어쓰기 자체가 입력되지 않았다..

 

따라서 getline 함수를 사용하여 띄워쓰기까지 모두 포함하여 엔터를 누르는 순간 입력받기를 끝낼 수 있도록 하였다.

 

getline 함수는 두 가지가 존재하는데, istream 라이브러리에 속하는 cin.getline() 함수와, string 라이브러리에 속하는 getline() 함수가 있다.

 

🐸 cin.getline() 함수는 마지막 글자가 '\0'인 c-string 을 입력받는데 사용하며, 세번째 매개변수 delim을 지정해주면, 해당 문자를 제한자로 두고, 그 직전까지 읽어와서 str에 저장해준다.

 

cin.getline(변수 주소, 최대 입력 가능 문자수, 종결 문자);
ex) cin.getline(str, 100);

 

🐸  getline() 함수는 최대 문자 수를 입력하지 않아도 되며, 원하는 구분자를 만날 때까지 모든 문자열을 받아 하나의 string 객체에 저장한다.

 

getline(입력스트림 오브젝트, 문자열을 저장할 string객체, 종결 문자);
ex) getline(cin, str);

 

나는 처음에 char word 변수에 띄워쓰기를 입력받고 싶었지만, 실패했었다.

🐸 그러나 char word; word = cin.get() 함수를 사용하면 문자 하나만 입력이 가능하며 공백과 개행도 입력으로 포함시킬 수 있다.

📌 괄호 개수 뿐만 아니라 순서까지 고려

처음 문제를 풀 땐, 그냥 ( 와 ) 의 개수, [ 와 ] 의 개수가 맞으면 되는 줄 알았는데 ( 가 열리면 ]로 닫히기 전에 ) 로 닫혀야한다는 순서규칙도 지켜져야 한다.

 

따라서 초반에는 소괄호를 위한 stack 하나와, 대괄호를 위한 stack 하나를 각각 선언하여 두 개의 stack을 이용해서 문제를 풀었다.

 

그러나, 순서 규칙을 따르기 위해선 하나의 stack에 괄호들을 담아야 하고, 닫힘 괄호( ')', ']' )를 입력받았을 때 stack의 최상단에 어떤 종류의 열린 괄호가 있는지를 판단하여 괄호 순서규칙이 맞는지를 구별하였다.

---

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

4949번: 균형잡힌 세상