4949번 균형잡힌 세상(C++)

C언어 까먹을까봐 오랜만에 실버 백준문제에 도전 그러나..얼떨결에 C++공부를 하게 되었다

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

4949번: 균형잡힌 세상

문제

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

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

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

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

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

사전지식

C로 해결이 도전히 안되었고, 알아보니 C++의 스택을 이용하면 그나마 쉽게 해결할 수 있다고 하더라.

기왕 된 김에 stack 라이브러리와, string 라이브러리에 들어있는 getline함수에 대해 알아보았다.

 

1. #include <stack>

스택은 나중에 넣은 것이 먼저 나오는 구조, 즉 LIFO(Last In First Out)의 구조를 띄고 있다.

괄호를 매칭하는 위 문제에 아주 적합한 구조라는 생각이 든다.

stack<int>A: 정수형을 담는 스택 A 선언

A.push(i): 스택 A에 i 추가

A.pop(): 스택 A의 top 삭제

A.top(): 스택 A의 top 리턴. 삭제는 되지 않음

A.empty(): 스택 A가 비어있으면 True, 그렇지 않으면 False 반환

A.size(): 스택 A의 크기 리턴

 

empty와 top이 내 관심의 대상이었는데, 아래 코드에서도 보면 !a.empty를 사용했다. 왜 그런지 궁금해서 a.empty를 빼고 코드를 작성해보았다.

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

int main() {
	stack<char>a;
	if (a.top()=='(') printf("hello");
}

실행 중 오류를 띄워주신다. 즉 빈 스택에 '너 top이 누구니?'라고 묻는 시도 자체가 불가능한 것인가 보다. 그래서 스택이 비어있을 경우 이런 오류가 발생할 수 있기 때문에, (!a.empty()&&a.top()=='(')이라고 미리 선수를 침으로써 오류 발생을 막아야 하는 것이다.

 

2. getline함수

string라이브러리에 있으며, getline(cin, string객체)이렇게 쓰면 '공백까지 포함하여' 문자열을 입력받을 수가 있겠다.

해결과정

https://cocoon1787.tistory.com/119

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

사실상 이 분 코드를 보고 하나하나 이해하는 데에 집중했다고 볼 수 있다...C언어로 했으면 코드가 꽤 길었을 것 같은데 너무 깔끔하게 C++로 구현을 해주셔서 그냥 그대로 배우기로 결심했다 스택 알려주셔서 감사합니다..

 

이해한대로 적어보자면

1. 문자열을 받고, 문자열 속 온점 바로 앞글자까지만 for문을 돌린다(ex) Happy Life. 에서 e까지만 검사)

2. for문의 내용은, 괄호를 발견할 시 stack a에 집어넣는다는 것. 여는 괄호는 집어넣는데 닫는 괄호가 나올 경우, stack의 top부분을 확인하여 짝 짓는 괄호가 있을 시 괄호를 pop해버린다. 아닐 시에는 no출력(마치 [][) 이런 상황) 

3. 온점 바로 앞, 즉 마지막 글자까지 도달했을 시 스택이 깨끗하게 비어있다면 yes출력, 아직도 해결되지 못한 괄호가 남아있다면 no출력

코드

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

int main() {
	string str;
	int i;

	while (1) {
		getline(cin, str);
		stack<char>a;
		if (str[0] == '.') break;

		for (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;
				}
			}
			if (str[i] == ')') {
				if (!a.empty()&&a.top() == '(') a.pop();
				else {
					printf("no\n"); break;
				}
			}
			if (a.empty() && i == str.length() - 2) printf("yes\n");
			else if (!a.empty() && i == str.length() - 2) printf("no\n");
		}

	}
}

결과

런타임 에러는 !a.empty를 뺐을 때 나타난 것이다