[백준 c++] 3986 좋은 단어

문제 설명

https://www.acmicpc.net/problem/3986
입력으로 주어진 단어가 문제에서 제시하는 "좋은 단어"인지 아닌지 판별하는 문제다.
1번 예시 처럼 같은 단어를 두개씩 묶었을 때 선이 겹치지 않아야 좋은 단어다.

아이디어

처음에 풀었을 때는 앞에서부터 같은 문자끼리 짝지었을 때 같은 문자끼리의 index 차이가 2가되면 좋은단어에서 탈락하는 것으로 코드를 짰는데 채점 20%에서 틀렸다고 나왔다..(내 방식대로 풀고싶어서 여러 인풋을 넣어봤는데 다 맞길래 이건 내가 해결할 수 없겠거니..풀이를 바꿨다^^;)

스택으로 풀면 더 간단하게 풀 수 있었다.

1. 문자열을 for문으로 하나씩 살펴보자
2. stack이 비어있지 않고(이 조건이 중요했다),
   stack.top()이 해당 문자와 동일하면 pop을 한다.
3. 맨 마지막에 stack이 전부 비워지면 좋은 단어다.

전체 코드

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

using namespace std;
int n,res;
string s;
int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> s;
		stack<char> p;
		for (char a:s) {
			if (p.size()&&a == p.top()) {
				p.pop();
			}
			else p.push(a);
		}
		if (p.empty()) res++;
	}
	cout << res;
}