[백준/BOJ] 4949번 균형잡힌 세상 (C/C++)

백준 온라인 저지(BOJ) 4949번 균형잡힌 세상

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

4949번: 균형잡힌 세상

* 사용언어 : C언어, C++

 

1. 문제

소괄호("()")와 대괄호("[]") 2종류를 포함하는 문자열이 주어짐

모든 괄호가 1:1 매칭되면서 짝을 이루는 균형잡힌 문자열인지 여부를 출력

 

2. 풀이

문자열을 순차적으로 읽어가면서 왼쪽 괄호가 나오면 Stack에 넣고(push),

오른쪽 괄호가 나오면 Stack의 top에 있는 문자열을 확인하고 제거(pop)하는 방식으로 구현했습니다.

괄호 외에 공백이나 알파벳은 균형잡힌 문자열 판단과 관련이 없으므로 처리하지 않고 넘어가면 됩니다.

 

 

오른쪽 괄호가 나왔을 때, 아래 3가지 중 하나라도 해당되면 균형잡힌 문자열이 아닌 것으로 판단했습니다.

1. Stack Size가 0일 때 (짝이 맞는 왼쪽 괄호가 없음)
2. 오른쪽 괄호가 ')' 인데, Stack의 Top이 '(' 이 아닐 때
3. 오른쪽 괄호가 ']' 인데, Stack의 Top이 '[' 이 아닐 때

 

문자열을 다 탐색한 후에는 왼쪽 괄호가 남은 경우를 잡아내야 하기 때문에 Stack Size를 확인했습니다.

(size가 0이 아니면 균형잡힌 문자열이 아님)

 

 

추가로 자주 사용하는 scanf는 '\0'(공백) or '\n'(enter)의 직전 문자까지 입력받으므로 이 문제에는 적합하지 않았습니다.

개행 전까지 모든 문자를 한 번에 입력받기 위해서 공백에서도 끊지 않고 문자로 입력받는 fgets를 사용했습니다.

 

참고로 fgets는 '\n' 문자까지 모든 문자를 입력받고, 그 뒤에 '\0'까지 추가해줍니다.

fgets로 예제 입력의 2번째 문장을 입력받은 경우

 

따라서 input 문자열의 크기를 102까지 해야 정답 처리가 됩니다.

 

변수 선언 순서에 따라 100개 혹은 101개로도 정답이 될 수 있으나

저는 101개로 제출했을 때 오답이었습니다.

LM == 102 정답, LM == 101 오답 ('\0'이 다른 변수 공간에 저장되면서 오류가 발생한 것으로 추정)

 

3. 코드

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
/*
4949_균형잡힌 세상
1116KB	4ms
*/
#include <cstdio>

const int LM = 102;
char str[LM], stack[LM], *c;
int size, isValid;

int main() {
#ifdef _WIN32
	freopen("input.txt", "r", stdin);
#endif // _WIN32
	while (1) {
		fgets(str, LM, stdin);
		c = str;
		if (*c == '.') break;

		size = 0, isValid = 1;
		while (*c != '.') {
			if (*c == '(' || *c == '[') stack[size++] = *c;
			else if (*c == ')' || *c == ']') {
				if (size == 0
					|| (*c == ')' && stack[size - 1] != '(')
					|| (*c == ']' && stack[size - 1] != '['))
				{
					isValid = 0;
					break;
				}
				--size;
			}
			++c;
		}

		if (isValid && !size) printf("yes\n");
		else printf("no\n");
	}
	return 0;
}