3986 - 좋은 단어

문제

코드

#include <bits/stdc++.h>
using namespace std;

int sum = 0;

int main(){
	stack<char> stack;
	int n;
	cin >> n;
	
	string m;
	
	for(int i = 0; i < n; i++){
		cin >> m;
	
		for(int j = 0; j < m.size(); j++){
		
		if(stack.empty()){
			stack.push(m[j]);
		
		}
		else if(stack.top() == m[j]){
			stack.pop();
		}	
		else{
			stack.push(m[j]);
		}
	}
	if(stack.empty()){
		sum++;
	}
	while( !stack.empty() ) stack.pop();
	}
	cout << sum;
	

		
		
}

풀이

문제를 해석해보면 전형적인 stack의 특징을 묻는 문제였다.
이어서 겹치지 않는다는게 생각하기 어려울 수 있지만
스택을 떠올려보면 테트리스랑 비슷하다고 생각이 들었다. 같은게 있을 때 pop() 시키고 아니면 push 하고 결국 stack이 비어 있으면 꼬임없이 연결된 것이다.
한 회순이 돌고 stack을 비워두는 것만 주의 한다면 쉽게 풀 수 있었다.

결과

후기

stack을 떠올리는게 핵심이었던 문제!