[ C++ ] #4949 균형잡힌 세상

 

괄호문제는 스택을 쓰는 대표적인 문제이다!

문자열을 하나씩 읽어서 괄호만 스택에서 관리해야겠다. 

 

나름 생각한대로 알고리즘을 짰는데,,, 시간초과가 났다.

---

먼저 간단하게 할 수 있는 것들부터 했다.

1. ios::sync_with_stdio(0);

2. cin.tie(0);

3. endl안쓰기

 

하지만 해결이 안됐고,, 결국 답지를 보면서 원인을 찾아봤다.

 

시간초과가 안나기 시작한건 char배열으로 getline을 받았는데

string으로 getline으로 받았다는 것과

이 변화에 따라서 for each문으로 바꾼것!이다.

 

그랬더니 틀렸습니다! 가 떴고 일단 시간초과가 안난것이 기뻤다 ㅎㅎ

그다음에 여러가지 반례를 찾아보고 열리는 괄호만 있을 때 안된다는 것을 발견했다!

 

그것만 고쳤더니 맞았습니다!를 만났다. 

 

#include<iostream>
#include<string>
#include<stack>

using namespace std;

int main() {

	ios::sync_with_stdio(0);
	cin.tie(0);


	while (1) {
		string charInput;
		getline(cin, charInput);
		if (charInput == ".") { return 0; }//종료
		stack<char> s;
		
		for (auto c: charInput) {
			if (c == '.') {
				if (s.empty()) {
					cout << "yes\n";
					break;
				}
				else {
					cout << "no\n";
					break;
				}

			}
			else if (c == '[' || c == '(') {
				s.push(c);
			}
			else if (c== ']'|| c== ')') {
				if (s.empty()) {
					cout << "no\n";
					break;
				}
				if ((s.top() == '['&&c == ']')||(s.top() == '(' && c == ')')) {
					s.pop();
				}
				else {
					cout << "no\n";
					break;
				}
			}
		}
	}
		return 0;
}