[BAEKJOON 4949] 균형잡힌 세상

4949번: 균형잡힌 세상 (acmicpc.net)

 

스택 응용 문제 중 하나이다.

어려운 내용은 딱히 없고, ( / [ 가 정상적인 종료인지만 확인하면 된다. 따라서, stack을 간단하게 생각하면 기본적인 구현이 가능하다.

 

예를 들면,

( -> [ -> ( 로 진입하는 문자열이라면, ) ->] -> ) 로 닫혀야 한다.

즉, 소스코드 작성 시와 동일하다고 보면 된다.

따라서 (, [ 일때 push, ), ] 일때 동일 형태의 input일때만 pop 을 하면 된다.

 

문제에 함정으로 좀 시간을 쓰게 되었는데,

stack 진입을 못 하는 조건에 대한 내용이 히든 케이스로 있다.

), ] 만 사용하는 코너 케이스를 확인하지 못하게 된다.

따라서 이 부분을 처리해 줘야 한다.

 

즉, 문제에서 주어진 예제는 다 통과하지만, 실제 수행에서 실패한다면

) .

를 추가해서 테스트 해 보면 된다.

 

int main() {

	while (true) {
		char word[101] = { '\0', };
		char stack[101] = { '\0', };
		int cur = 0, sptr = 0;
		bool debug = true;

		cin.getline(word, 101);
		if (word[0] == '.') break;
		
		while (word[cur] != '.') {
			if (word[cur] == '(' || word[cur] == '[') {
				stack[sptr++] = word[cur];
			}
			else if (word[cur] == ')'){
				if (stack[sptr - 1] == '(')
					stack[--sptr] = '\0';
				else debug = false;
			}
			else if (word[cur] == ']') {
				if (stack[sptr -1] == '[')
					stack[--sptr] = '\0';
				else debug = false;
			}
			cur++;
		}
		cout << ((sptr == 0 && debug == true) ? "yes" : "no") << endl;
	}
	return 0;
}