백준3986 - 좋은단어

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

3986번: 좋은 단어

스택을 활용하여 푸는 문제이다.

문자를 한 개씩 스택에 넣고 top에서 같은 문자를 만나면 빼주는 형식으로 구현하였다.

좋은 단어의 경우이면 문장 전체를 순회하였을 때 스택은 비어있어야 한다는 생각을 하였다.

생각보다 간단한 문제였는데 많이 해맸다ㅜㅜ.

문제를 풀기 전에 항상 설계를 먼저하는 습관을 길러야겠다.

 

#include <iostream>
#include <stack>
#include <string>
using namespace std;


int main() {
	int n; //입력할 문장의 수
	int cnt = 0; //답을 저장할 변수
	cin >> n;
    
    
	while (n--) {
		stack<char> stk; //스택을 활용!
		string s;
		cin >> s;
		for (unsigned int i = 0; i < s.size(); i++) { //문장의 길이만큼 반복
			if (stk.size() == 0) { //스택에 아무것도 들어있지 않다면
				stk.push(s[i]); //push를 한다.
			}
			else { //무언가 들어있으면
				if (stk.top() == s[i]) { //스택의 탑과 현재 인덱스가 가리키는 문장의 문자가 같으면				
                    stk.pop(); //팝
				}
				else { //스택의 탑과 현재 인덱스가 가리키는 문장의 문자가 같지 않으면
					stk.push(s[i]); //푸쉬
				}
			}
		}
		if (stk.size() == 0) { //스택이 비어있으면
			cnt++; //답을 저장할 변수 1증가
		}
	}
    
   	cout << cnt;
}