[백준 3986] 좋은 단어 (C++)

1. 문제

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

3986번: 좋은 단어

A와 B를 입력받고 같은 문자끼리 짝을 짓는 문제이다. 이때 아치형 곡선을 그어 서로의 곡선이 겹치지 않게 만든다

 

 

2. 풀이

아치형 곡선을 그어 서로의 곡선이 겹치지 않게 만든다는 말은 다음과 같이 바꿔 해석할 수 있다.

 

• 홀수 번째 입력받은 A를 ' ( '로, 짝수 번째 입력받은 A를 ' ) '로 치환하여 괄호쌍을 짝짓는 문제로도 볼 수 있다.

마찬가지로 B도

• 홀수 번째 입력받은 B를 ' [ '로, 짝수 번째 입력받은 B를 ' ] '로 치환하여 괄호쌍을 짝지을 수 있다.

즉 stack을 활용하는 전형적인 괄호쌍문제이다.

 

예시

예를 들어 입력값이 ABAB일 경우 "(   [   )   ]" 로 볼 수 있으므로 짝이 안맞아 좋은 단어가 아니다.

반면에 입력값이 BAABBB인 경우 "[   (   )   [   ]   ]" 로 볼 수 있으므로 짝이 맞아 좋은 단어이다.

 

 

괄호쌍의 자세한 풀이는 "[백준 4949번] 균형잡힌 세상"을 참고하면 더 쉽게 이해할 수 있다.

https://wondrous-developer.tistory.com/2

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

 

3. 코드

stack의 자료구조를 이용하여 풀어 구현한다.

#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);
	int T;
	int sum = 0;
	cin >> T;
	while (T--) {
		cin >> str;
		int len = str.length();
		int index = 0;
		while (index < len) {
			if (sta.empty()) {
				sta.push(str[index++]);
				continue;
			}
			if (sta.top() == str[index]) sta.pop();
			else sta.push(str[index]);
			index++;
		}
		if (sta.empty()) sum++;
		while (!sta.empty()) {
			sta.pop();
		}
	}
	cout << sum;
	return 0;
}