[알고리즘] 백준 BOJ 3986 좋은단어 풀이 및 코드

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

3986번: 좋은 단어

설명

같은 글자를 짝지어 주는 문제입니다. 아치형으로 서로 짝을 지어주고 모든 짝을 지어줄 수 있다면 그 단어는 좋은 단어라고 합니다. 단, 아치형이 서로 겹치지 않게 짝을 이뤄줘야합니다. 아래의 그림을 보면 바로 이해가 가실겁니다.

다음의 경우에는 좋은 단어입니다. 아치형이 겹치지 않죠

 

좋은단어

 

아래의 경우는 아치가 겹치므로 좋은단어가 아닙니다.

안좋은 단어

 

풀이

이 문제의 힌트는 바로 스택을 활용한 괄호 짝 맞추기 문제입니다. 가장 최근에 나온 짝이 자신의 짝인지 확인하는 문제와 컨셉이 같은데요. 여기서 괄호( '(', ')' )만 살짝 'A','B'로 바꾼것일 뿐입니다.

ABBA를 예로 들겠습니다.

1. A는 스택이 이미 비어있으니 스택에 집어넣습니다. (현재 스택 - A)

2. B는 스택 꼭대기 글자가 A이므로 B는 스택이 저장합니다. (현재 스택 - A B)

3. B는 스택 top의 글자가 B이므로 이전의 B를 스택에서 pop합니다. (현재 스택 - A)

4. A는 현재 스택 top의 글자와 같으므로 A를 스택에서 pop합니다. (현재 스택 - ' ' )

 

코드

아래는 전체 문제 풀이 코드입니다.

#include <cstdio>
#include <stack>
#include <string.h>
using namespace std;

char str[100001];
int n;
int main() {

	int ans = 0;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%s", str);
		stack<char> st;
		int m = strlen(str);
		for (int j = 0; j < m; j++) {
			if (!st.empty()&&st.top()==str[j]) st.pop();
			else st.push(str[j]);
		}
		if (st.empty()) ans++;
	}
	printf("%d\n", ans);
}

 

어렵지 않게 코드가 이해가실거라 생각합니다.