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

4949번: 균형잡힌 세상

이 문제는 이전에 풀었던 9012번: 괄호의 응용 문제다.

그 때와 다른 점은 대괄호가 추가 되었다는 점.

그래서 그에 대한 int 값 하나만 더 추가하면 되는거 아닌가?라고 생각했던 건 큰 오산이었다.

([)]이렇게 괄호 안에 불완전한 괄호가 있으면 안 된다. 위와 같은 방법으로는 판독할 수 없다.

하지만 생각할 수 있는 무적의 방법이 있다.

한 쌍을 이루는 괄호가 인접해 있는 경우를 계속 지우다 보면 균형잡힌 문장에서는 결국 모두 없어지지만 균형잡히지 않은 문장에서는 괄호가 남는 것을 알 수 있다. 이를 적용하면 된다.

말은 쉽지만 막상 이를 구현하려니 쉽지 않다.

걸핏하면 메모리 접근 오류가 발생하니 말이다.

단계별로 생각해보자.

 

1. 입력

이 문제에서 입력은 여러 줄에 걸쳐서 될 수도 있다.

하지만 종결조건이 점 하나로 정해져 있으니, 이를 활용하면 될 것이다. 

scanf의 서식문자를 %[^.]와 같이 적으면 .이 있는 문자까지 한 번에 입력받는다.

%[^.]로 입력을 받으면 입력버퍼에 .과 \n이 남게 된다.  이를 지워주기 위해, getchar();를 두 번 적어줬다.

#include <cstdio>

using namespace std;

int main() {
	while (true) {
		char str[101];
		for (int i = 0; i < 101; i++) {
			str[i] = 0;
		}
		scanf("%[^.]", str);
		getchar();
		getchar();
		if (str[0] == 0)
			break;
		printf("%s\n", str);
	}
	return 0;
}

위 코드에서 예제를 입력하면, 아래처럼 정상적으로 출력이 된다.

So when I die (the [first] I will see in (heaven) is a score list)
[ first in ] ( first out )
Half Moon tonight (At least it is better than no Moon at all]
A rope may form )( a trail in a maze
Help( I[m being held prisoner in a fortune cookie factory)]
([ (([( [ ] ) ( ) (( ))] )) ])
 

 

2. 불필요한 문자 제거

다음으로 할 일은 "()[]"을 제외한 나머지 문자는 불필요하므로 없애는 것이다.

새로운 문자열 extract를 선언하고 초기화해주면서, str에서 문자를 추출해 값을 넣었다.

#include <cstdio>

using namespace std;

int main() {
	while (true) {
		// Step 1. get sentence
		char str[101];
		for (int i = 0; i < 101; i++) {
			str[i] = 0;
		}
		scanf("%[^.]", str);
		getchar();
		getchar();
		if (str[0] == 0)
			break;

		// Step 2. eliminate unneccessary characters
		char extract[101];
		int index = 0;
		for (int i = 0; i < 101; i++) {
			extract[i] = 0;
			while (str[index] != 0) {
				if (str[index] == '(' || str[index] == ')' ||
					str[index] == '[' || str[index] == ']') {
					extract[i] = str[index];
					index++;
					break;
				}
				index++;
			}
		}
		printf("%s\n", extract);
	}
	return 0;
}

이제 예제를 넣어보면 아래와 같이 잘 출력이 된다.

([]())
[]()
(]
)(
([)]
([(([([])()(())]))])

 

3. 인접하며 짝을 이루는 괄호 제거

이는 extract 배열의 0번 인덱스부터 쭉 스캔해가며 짝을 이루는 괄호가 발견되면 그 시작위치 + 2의 요소부터 앞으로 두 칸씩 덮어씌우면 된다. 이를 짝이 발견되지 않을 때까지 반복한 후, extract가 비어있으면 "yes"를, 아니면 "no"를 출력하면 끝이다.

#include <cstdio>

using namespace std;

int main() {
	while (true) {
		// Step 1. get sentence
		char str[101];
		for (int i = 0; i < 101; i++) {
			str[i] = 0;
		}
		scanf("%[^.]", str);
		getchar();
		getchar();
		if (str[0] == 0)
			break;

		// Step 2. eliminate unneccessary characters
		char extract[101];
		int index = 0;
		for (int i = 0; i < 101; i++) {
			extract[i] = 0;
			while (str[index] != 0) {
				if (str[index] == '(' || str[index] == ')' ||
					str[index] == '[' || str[index] == ']') {
					extract[i] = str[index];
					index++;
					break;
				}
				index++;
			}
		}
		
		// Step 3. simplify
		bool found = true;
		while (found) {
			found = false;
			for (int i = 0; extract[i] != 0; i++) {
				if ((extract[i] == '(' && extract[i + 1] == ')') ||
					(extract[i] == '[' && extract[i + 1] == ']')) {
					found = true;
					for (int j = i; extract[j] != 0; j++) {
						extract[j] = extract[j + 1];
					}
					for (int j = i; extract[j] != 0; j++) {
						extract[j] = extract[j + 1];
					}
				}
			}
		}
		if (extract[0] == 0)
			printf("yes\n");
		else
			printf("no\n");
	}
	return 0;
}

예제를 넣으니 결과도 잘 나온다.

yes
yes
no
no
no
yes
yes

 

이번 문제를 풀면서 scanf의 [set] 서식문자를 활용할 때 입력의 끝으로 지정한 문자가 입력버퍼에 남아 문제를 일으켜 한동안 애먹었었다. 또한, 인접한 괄호 짝을 제거하는데 처음엔 벡터를 이용했다가 메모리 접근오류가 계속 떠서 고생했는데, 그냥 그럴땐 일반 배열을 활용하는게 나은 것 같다. 괜찮은 문제였다.