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

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

4949번: 균형잡힌 세상

- 서론 

스택을 활용하는 문제 였습니다.

 

 문제의 조건은 소괄호와 대괄호가 제대로 닫혀 있는지를 체크하는 문제로

복잡하지 않았습니다.

 문제를 읽자마자 어디선가 풀어봤던 기억이 나서 익숙 했습니다.

 

 이런식으로 메모장에 기록해서 생각을 정리 하였습니다.

복잡하지 않게 구현 할 수 있을 것 같지만 약간 생각이 필요했던 부분이 있었습니다.

 

 프로그램의 기능은 간단히 생각해보면 문장을 입력받고 해당 문장이 조건에 맞으면 yes 틀리다면 no 를

출력해야 하는데, 조건이 틀린 모든 경우에 대해 정리 하는 것이었습니다. 그래서 정리하자면,

 

1. 열린 괄호가 없는데 닫힌 괄호가 나온경우

2. 열린 괄호가 있는데 문장이 끝난 경우

3. 이전에 열린 괄호와 이번에 닫히는 괄호 종류가(대괄호, 소괄호) 맞지 않는 경우

 

이렇게 총 3가지에 대해 정리할 수 있었다.

 

- 코드

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

using namespace std;


int main() {
	
	string str;
	vector<char> stack;

	while(1) {

		getline(cin, str);
		if (str[0] == '.')
			break;


		for (int j = 0; j < str.size(); j++) {

			if (str[j] == '(' || str[j] == '[') { // 스택에 추가
				if (str[j] == '(') {
					stack.push_back('(');
				}
				else if (str[j] == '[') {
					stack.push_back('[');
				}
				
			}
			else if (str[j] == ')' || str[j] == ']') { // 스택에서 제거

				if (stack.size() != 0) { // 스택에서 빼내기 전에 스택이 있는지 검사

					if (str[j] == ')' && stack.back() == '(' ) {
						stack.pop_back();
					}
					else if (str[j] == ']' && stack.back() == '[') {
						stack.pop_back();
					} 
					else { // 괄호의 순서가 맞지 않는 경우
						break; // 스택 남긴채 검사 종료
					}

				}
				else { // 스택에 아무것도 없는데 빼내야 하는 경우
					stack.push_back('d'); // 스택에 더미데이터 추가 후 검사 종료
					break;
				}
			}

			
		}

		if (stack.size() != 0) { // 검사 이후에도 스택이 남아있다면 불균형한 문장
			cout << "no\n";
		}
		else { // 검사 이후 스택이 비었다면 균형잡힌 문장
			cout << "yes\n";
		}

		stack.clear();
	}

	return 0;
}

 

 앞서 얘기한 내용을 바탕으로 구현한 코드 입니다.

코드에 대해서 추가적으로 설명한 부분은, 코드의 마지막 부분에서

스택에 괄호가 남아 있다면 no, 스택에 괄호가 없다면 yes 를 출력하도록 했는데,

 

 앞서 언급한 2번 조건의 경우 no를 출력해야 하지만 스택이 비게 되어서 어찌 처리 해야 하나 고민을 했습니다.

그래서 더미 데이터를 추가하고 탐색을 종료하는 식으로 처리 했습니다.

 

사실 더미 데이터를 추가 하는 방법 이전에 뭐 no를 출력 먼저 하고 bool 타입 변수를 이용해서

continue를 해야 하나 고민을 했었는데, 좀만 더 생각해보니 아무 글자나 하나 추가 하면 될 것 같다는 생각을 떠올릴 수 있었습니다.

 

역시 복잡한 코드와 간단한 코드는 정말 한 끗 차이다.