[C/C++] 백준 4949번 균형잡힌 세상(Stack)

 

문제

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

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

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

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

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

입력

하나 또는 여러줄에 걸쳐서 문자열이 주어진다. 각 문자열은 영문 알파벳, 공백, 소괄호("( )") 대괄호("[ ]")등으로 이루어져 있으며, 길이는 100글자보다 작거나 같다.

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

출력

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

 

<코드>

#include<iostream>
#include<stdio.h>
#include<string>
#include<stack>

using namespace std;
string str;

/* 입력예제
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)].
([ (([( [ ] ) ( ) (( ))] )) ]).
 .
.
*/

int main()
{
	while (1)
	{
		getline(cin, str); // 공백까지 입력받아야 하므로 scanf사용은 부적절하다고 생각했습니다.
		stack<char> a;
		if (str[0] == '.') break;

		for (int i = 0; i < str.length() - 1; i++)
		{
			if (str[i] == '(') a.push('(');
			if (str[i] == '[') a.push('[');
			if (str[i] == ']')
			{
				if (!a.empty() && a.top() == '[') a.pop();
				else { printf("no\n"); break; } // "]hello[" 같은 예외 문장들 방지
			}

			if (str[i] == ')')
			{
				if (!a.empty() && a.top() == '(') a.pop();
				else { printf("no\n"); break; } // ")hello(" 같은 예외 문장들 방지
			}

			if (a.empty() && i == str.length() - 2) printf("yes\n"); // str[str.length() - 1] = '.' 이므로 검사할 필요가 없다.
			else if (!a.empty() && i == str.length() - 2) printf("no\n");
		}

	}
}

 

1달전에 스택에 대한 개념도 없었고 구현할 줄도 몰라서 어떻게 풀어나가야 할 지 몰랐었던 문제였습니다. 처음에는 scanf로 입력을 받으려고 scanf("%[^\n]s", str) 이런식으로 공백처리때문에 힘빼다가 scanf 사용은 부적절한거 같아서 getline()함수로 문자열을 입력 받고 length()함수로 문자열의 길이를 구하였습니다.

문제풀이의 기본핵심을 말씀드리자면 

"((Hello)[world])." 라는 문장이 있다고 가정을 하면 괄호는 (  (   )   [    ] ) 이런식으로 구성되어 있고 문자열의 길이는 17입니다. 그리고 for문을 돌면서 a라는 스택에는 왼쪽 소괄호("(")가 2개 쌓이게 됩니다.

a

(

(

 

 

그 후 오른쪽 소괄호(")") 가 나타나기 때문에 스택 맨 뒤에 있던 왼쪽 소괄호("(")와 짝을 짓고 없애줍니다.

a

(

 

 

다시 왼쪽 대괄호("[") 가 나타났기 때문에 a라는 스택에 왼쪽 대괄호("[")를 쌓습니다.

a

(

[

 

 

그 후 오른쪽 대괄호("]") 가 나타나기 때문에 스택 맨 뒤에 있던 왼쪽 대괄호("[")와 짝을 짓고 없애줍니다.

a

(

 

 

마지막으로 오른쪽 소괄호(")") 가 나타났기 때문에 a라는 스택에 남아있던 왼쪽 소괄호(")")와 짝을 짓고 없애줍니다.

a

 

 

a라는 스택이 for문을 다 돌고 나서 비어있으므로 "yes"를 출력 하고,

스택에 요소가 남아있을 경우에는 "no"를 출력합니다(ex : 문자열"( ( )."의 경우 스택 a에 "("이 남아있게됨).

"][" 이나 ")(" 문자열 같은 예외의 경우도 고려하여 for문을 돌면서 break 할 수 있게 코딩하였습니다.  

 

 

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

4949번: 균형잡힌 세상