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

깔끔하게 구현한 최종 코드는 맨 아래에 정리해 두었다.

1. 문제

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

4949번: 균형잡힌 세상

괄호쌍의 유효성을 검사하는 문제이다.

 

2. 풀이

문자열을 탐색하며 열린 괄호( ' ( ' 또는  ' [  ' )가 닫힌 괄호( ' ) ' 또는  ' ]  ' )와 만날 때마다 짝을 지어서 준다. 이 과정에서 자료구조의 스택(stack)을 활용하면 효율적으로 풀 수 있다. 

방법

1. 열린 괄호( ' ( ' 또는  ' [  ' )가 나오면 stack에 차례대로 추가한다.
   
2. 닫힌 괄호( ' ) ' 또는  ' ]  ' ) 가 입력될 경우 비교를 위해 stack이 비어있으면 추가하고 stack의 top과 비교하여 쌍이 맞을 경우에 stack에서 제거한다.
3. 1회의 탐색 후 stack이 비어있으면 모두 쌍이 맞아서 사라진 것이고, stack이 비어있지 않으면 쌍이 맞지 않은 경우이다.

다음의 입력 예시를 통해 stack에서 괄호가 추가되고, 제거되는 과정을 보면 다음과 같다.

입력1: [   (   [   ]   )   ]

입력2: [   (   ]   )

 

위의 알고리즘을 실행하면 입력1의 경우 stack은 다음과 같다.

1) ' [ ' 추가
→ stack:  [ 

2) ' ( ' 추가
→ stack:  [   (

3) ' [ ' 추가
→ stack:  [   (   [

4) 괄호 쌍 확인 후 ' [ ' 제거하기
→ stack:  [   (   [   ]  괄호쌍 확인 후 짝이 맞으므로 제거 → stack:   [   (

5) 괄호 쌍 확인 후 ' ( ' 제거하기
→ stack:  [   (   ) 괄호쌍 확인 후 짝이 맞으므로 제거 →  stack:   [ 

6) 괄호 쌍 확인 후 ' ( ' 제거하기
→ stack:  [   ] 괄호쌍 확인 후 짝이 맞으므로 제거 →  stack:   empty

입력2의 경우는 다음과 같다.

1) ' [ ' 추가
→ stack:   [ 
2) ' ( ' 추가
→ stack:   [   (

3) 괄호쌍 확인 후 짝이 맞지 않으므로 stack유지
→ stack:  [   (   ] 괄호 쌍 확인 후 짝이 맞지 않으므로 유지 → stack:  [   (

4) 괄호쌍 확인 후 짝이 맞지 않으므로 stack유지
→ stack:  [   (   ] 괄호 쌍 확인 후 짝이 맞지 않으므로 유지 → stack:  [   (

따라서 경우1은 짝이 맞으므로 탐색 후 stack이 비어있게 되고 경우2는 짝이 맞지 않으므로 탐색 후 stack이 차있다.

3. 코드

1) 처음에 작성한 코드

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

using namespace std;

stack<char> sta;


string str;

int main(void) {
	cin.tie(0);
	ios::sync_with_stdio(false);

	while (1) {

		bool check = true;
		getline(cin, str);
		if (str == ".")break;

		int index = 0;
		while (str[index] != '.') {
			if (str[index] == '[' || str[index] == '(') sta.push(str[index]);
			if (str[index] == ']' || str[index] == ')') {
				if (sta.empty()) {
					check = false;
					break;
				}
				else if (sta.top() == '[' && str[index] == ']' ||
					sta.top() == '(' && str[index] == ')') sta.pop();
                    
			}
			index++;
		}
		if (!sta.empty()) check = false;
		if (check == true) cout << "yes\n";
		else cout << "no\n";

		while (!sta.empty()) {
			sta.pop();
		}

	}
	return 0;
}

하지만 틀렸다고 나와서 반례를 찾다가 못찾겠어서 랜덤함수를 이용하여 무작위로 괄호들을 생성하여 테스트해본 결과 반례를 찾을 수 있었다.

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

using namespace std;

stack<char> sta;


string str;
char test[4] = { '(', '[', ')', ']' };

int main(void) {
	cin.tie(0);
	ios::sync_with_stdio(false);
	srand(time(NULL));
	
	int T = 100;
	while (T--) {

		bool check = true;
		//getline(cin, str);
		int length = rand() % 9 + 1;
		for (int i = 0; i < length; i++) {
			str.push_back(test[rand() % 4]);
		}
		str.push_back('.');
		//if (str == ".")break;
		cout << "sring: " << str << "->";
		
		int index = 0;
		while (str[index] != '.') {
			if (str[index] == '[' || str[index] == '(') sta.push(str[index]);
			if (str[index] == ']' || str[index] == ')') {
				if (sta.empty()) {
					check = false;
					break;
				}
				else if (sta.top() == '[' && str[index] == ']' ||
					sta.top() == '(' && str[index] == ')') sta.pop();
			}
			index++;
		}
		if (!sta.empty()) check = false;
		if (check == true) cout << "yes\n";
		else cout << "no\n";

		while (!sta.empty()) {
			sta.pop();
		}
		while (!str.empty()) {
			str.pop_back();
		}
	
	}
	return 0;
}

100번의 무작위 실행을 통하여 얻은 반레

따라서 완성된 코드는 다음과 같다.

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

using namespace std;

stack<char> sta;


string str;

int main(void) {
	cin.tie(0);
	ios::sync_with_stdio(false);

	while (1) {

		bool check = true;
		getline(cin, str);
		if (str == ".")break;

		int index = 0;
		while (str[index] != '.') {
			if (str[index] == '[' || str[index] == '(') sta.push(str[index]);
			if (str[index] == ']' || str[index] == ')') {
				if (sta.empty()) {
					check = false;
					break;
				}
				else if (sta.top() == '[' && str[index] == ']' ||
					sta.top() == '(' && str[index] == ')') sta.pop();

				else {
					check = false;
					break;
				}
			}
			index++;
		}
		if (!sta.empty()) check = false;
		if (check == true) cout << "yes\n";
		else cout << "no\n";

		while (!sta.empty()) {
			sta.pop();
		}

	}
	return 0;
}

 

2) 정리한 정답 코드

위의 방법대로 코드를 작성하면 if문이 중첩되고 문제가 복잡해질 경우 하나하나 모든 경우를 고려하기에는 불가능하다. 골드3정도 되는 문제만 해도 if문으로 case를 고려하면 코드가 많이 복잡해진다. 따라서 일반성을 고려하여 단순하게 stark의 자료구조 하나만으로 깔끔하게 구현한 코드는 다음과 같다.

#define CASE1(x) ((x == '(') || (x == '['))
#define CASE2(x) ((x == ')') || (x == ']'))
#define CASE3(x, y) ((x == ']') && (y == '[') || (x == ')') && (y == '('))

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

using namespace std;

stack<char> sta;
string str;

int main(void) {
	cin.tie(0);
	ios::sync_with_stdio(false);

	while (1) {
		getline(cin, str);
		if (str == ".") break;
		int index = 0;
		while (str[index] != '.') {
			if (CASE1(str[index])) sta.push(str[index]);
			if (CASE2(str[index])) {
				if (sta.empty()) sta.push(str[index]);
				if (CASE3(str[index], sta.top())) sta.pop();
				else sta.push(str[index]);
			}
			index++;
		}
		if (sta.empty()) cout << "yes\n";
		else cout << "no\n";
		while (!sta.empty()) {
			sta.pop();
		}
	}
	return 0;
}

간단하게 복잡한 조건식은 매크로 함수로 구현하였고 check의 유뮤를 확인하지 않고 stack의 비어있는지의 유무로 결과를 판단하였다.