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

1. 문제

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

4949번: 균형잡힌 세상

---

2. 문제 풀이

#include <iostream>
#include <bits/stdc++.h>
#pragma warning (disable:4996)

using namespace std;

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

	while (1) {
		stack<int> stack;
		string s;
		int flag = 0;
		getline(cin,s);
		if (s == ".") break;
		for (int i = 0; i < s.size(); i++) {
			if (s[i] == '(' || s[i] == '[')
				stack.push(s[i]);
			else if (s[i] == ')') {
				if (stack.empty()) {
					flag = 1; break; // )))) answer : no
				}
				else if (stack.top() == '(')
					stack.pop();
				else {
					flag = 1; break; // ((])) answer : no
				}
			}
			else if (s[i] == ']') {
				if (stack.empty()) {
					flag = 1; break; // ]]]] answer : no
				}
				else if (stack.top() == '[')
					stack.pop();
				else {
					flag = 1; break; // [[)]] answer : no
				}
			}
		}

		if (flag == 1)
			cout << "no\n";
		else if (stack.empty())
			cout << "yes\n";
		else
			cout << "no\n";
	}
}

---

3. 문제 평가 및 해설

스택을 이용한 기초적인 문제인데, 살짝 꼬은 느낌이다.

문제 해설은 다음과 같다.

1. '('과 '[' 를 만나면 stack에 push한다.

2. ')'과 ']'를 만나면 stack에 pop한다. 이때 stack의 top과 비교해야한다. 예를 들어 ')'를 만났다고 하면 스택의 top에 '('가 존재해야지, pop을 할 수 있다. '['도 동일한 방법으로 처리해주면 된다.

한번에 "맞았습니다!"가 나오지 않을 문제일 수 있다. 왜냐하면 반례가 은근 많다.

반례에 대한 예외처리를 해줘야하는데, 코드의 주석에 반례의 경우와 예외처리 코드를 달아놨다.

나의 첫 코드의 반례는 다음과 같다.

Input : ))))

Answer : no

 

Input : (([)) 

Answer : no