[알고리즘/문제풀이/BOJ 4949번] 균형잡힌 세상

균형잡힌 세상 문제는 스택을 활용하여 해결할 수 있습니다. 지문 중 '짝을 이루는 두 괄호가 있을 때, 그 사이에 있는 문자열도 균형이 잡혀야 한다.'라는 문구가 LIFO 자료구조인 스택의 사용을 암시하고 있습니다. 따라서 괄호 문제와 비슷하게 풀 수 있으나 소괄호와 대괄호를 구분하는 부분만을 추가해주면 됩니다. 주의할 점은 마지막에 .을 붙임으로써 프로그램을 끝낼 수 있다고 하였는 데 .뒤에 어떠한 문자열이 없다고 맹신하여서는 안된다. 즉 EOF를 조건으로 끝내도록 하면 틀릴 수도 있다는 것이다.

작성한 코드는 다음과 같다.

---

#include<stdio.h>
//https://ark-hive.tistory.com/
char character;
//소괄호, 대괄호 구분, top=0이 되어야 함. 괄호 사이의 문자열의 균형 - 스택 의도
char stack[100];
int top = 0;
int newline = 0;

void push(char ch) {
	top += 1;
	stack[top] = ch;
}

char pop() {
	if (top == 0) return -1;
	else {
		top = top - 1;
		return stack[top+1];
	}
}

int main(void) {
	while (character = getchar()) {
		if (newline == 1) {
			if (character == '.') break;
			else newline = 0;
		}
		if (character == '(' || character == '[') {
			push(character);
		}
		else if (character == ')') {
			if (pop() != '(') {
				printf("no\n");
				top = 0;
				while (character = getchar()) {
					if (character == '\n') break;
				}
			}
		}
		else if (character == ']') {
			if (pop() != '[') {
				printf("no\n");
				top = 0;
				while (character = getchar()) {
					if (character == '\n') break;
				}
			}
		}
		else if (character == '\n') {
			if (top != 0) printf("no\n");
			else {
				printf("yes\n");
			}
			newline = 1;
			top = 0;
		}
		else if (character == EOF) break;
	}
}

문제의 지문은 다음 링크에서 확인할 수 있습니다.

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