[백준/c++] 4949 - 균형잡힌 세상

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

4949번: 균형잡힌 세상

---

1) 풀이

오늘은 개인적으로 몸이 안 좋아서

풀이가 상당히 횡설수설일 수 있으나

하루에 한 개는 꼭 풀고 올리자는 다짐을 져버릴 수는

없어서 한 번 올려본다... 너무 읽기 힘들면

나중에 수정하는 수밖에... 😥

 

아무튼!

이 문제는 스택을 이용하여 소괄호와 대괄호의 짝을 지어주어

짝이 맞으면 "yes"를, 맞지 않으면 "no"를 출력해주는 

비교적 간단한 문제이다.

 

'짝을 지어준다'라는 개념이 조금 생소할 수도 있으니

조금의 설명을 덧붙이자면 다음과 같다.

 

1) 여는 괄호 , 즉 이 문제에서 ( 나 [ 가 나오면 스택에 저장한다.

2) 닫는 괄호 , 즉 이 문제에서 ) 나 ] 가 나오면

스택의 top을 확인하여 각각의 닫는 괄호와 짝지어지는 괄호가 맞는지 확인하고,

맞으면 pop을, 아니라면 균형이 맞지 않으므로 확인을 종료한다.

 

또한 문자열이 한개, 혹은 여러개 주어지는데

해당 문장이 균형잡힌지 알아보기 위해서는

한 문장씩 확인해야 하기 때문에 getline함수를 사용하여

마지막 종료조건 ","이 들어오기 전까지 문장을 한줄씩 string변수에 입력해준다.

(getline함수에 대한 설명은 게시글 맨 하단 참고자료에)

 

문장을 모두 입력받았다면 위에서 설명한 '괄호를 짝지어주는 방법'으로

스택에 괄호를 넣고 빼는 것을 반복한다.

그 과정 내에서 균형이 맞는지 아닌지를 판단하는 boolean 변수를

이용하여 최종적으로 "yes"를 출력할지, "no"를 출력할지 결정지어 준다.

 

이때 주의해야 할 점은, 

1) 닫는 괄호가 나왔는데 , 스택이 비어있다.

2) 문장 내의 문자를 다 살펴보았는데 스택이 비어있지 않다.

 

이 두 경우도 균형이 맞지 않는 경우이므로 마지막까지 스택이 비어있는지 여부를 확인해줘야 한다!

 

2) 최종 소스코드

#include <bits/stdc++.h>
using namespace std;
string s; //입력받을 문장
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
		while (true) {
			getline(cin, s);
			if (s == ".") break; 
			stack<char>st; //괄호 저장할 스택
			bool isTrue = 1; //균형잡혀 있는지, 아닌지를 판단해주는 boolean 변수
			for (auto c : s) {
				if (c == '(' || c == '[') {
					st.push(c);
				}
				else if (c == ')') {
					if (st.empty()||st.top() != '(') {
						isTrue = 0;
						break;
					}
					st.pop();
				}
				else if (c == ']') {
					if (st.empty() || st.top() != '[') {
						isTrue = 0;
						break;
					}
					st.pop();
				}
				else continue;
			}

			if (!st.empty()) { //괄호의 짝이 다 맞았어도
								//스택에 남아있는 괄호가 있으면 균형X
				isTrue = 0;
			}
			if (isTrue==1) { 
				cout << "yes" << '\n';
			}
			else cout << "no" << '\n';
			
		}
	

}

3) 참고자료

modoocode.com/236