[백준 3986] 좋은단어 cpp-py

문제
A와 B로만 이루어진 글자가 있다. 단어 중에서 같은 글자끼리 글자위로 아치형 곡선을 그었을 때 아치형 곡선이 교차하지 않으면 좋은단어이다. N개의 단어 중 좋은 단어가 몇 개인지 출력하라.

입력
첫째 줄에 단어의 수 N이 주어진다.
다음 N개의 줄에 A와 B로만 이루어진 단어가 한 줄씩 입력된다.

출력
좋은 단어의 개수를 출력한다.

---

C++

같은 글자끼리 글자 위로 아치형 곡선을 그었을 때 교차가되지 않는 조건은 가운데를 기준으로 대칭일 때이다. 대칭을 판단하기 위해 스택을 활용한다.

1. N개의 단어를 입력받을 때마다 다음을 반복한다.

2. 글자를 입력받고 처음부터 탐색을 진행한다.

3. 현재 스택이 비어있으면 현재 글자를 push()한다.

3. 비어있지 않다면 스택의 top()과 비교하고 현재 글자와 같다면 스택을 pop()한다.

3. 비어있지 않고 스택의 top()과 다르다면 현재 글자를 스택에 push()한다.

4. 3의 과정을 입력된 글자의 끝까지 탐색했을 때도 스택이 비어있으면 최종해를 증가시킨다. 만약 대칭이라면 위의 과정을 거쳤을 때 스택이 비어있을 것이다.

#include "pch.h"
#include <iostream>
#include <stack>
#include <string>
using namespace std;
int main()
{
	int test_case;
	int answer = 0;
	cin >> test_case;

	while (test_case--) {
		stack<char> st;
		string word;
		cin >> word;

		for (int i = 0; i < word.length(); i++) {
			if (st.empty()) {
				st.push(word[i]);
			}
			else {
				if (st.top() == word[i]) {
					st.pop();
				}
				else {
					st.push(word[i]);
				}
			}
		}
		if (st.empty())
			answer++;
	}

	cout << answer << endl;
	return 0;
}

 

python

리스트를 스택으로 활용할 수 있다. 

test_case = int(input())
result = 0
while test_case:
    word = input()
    check = []
    
    for w in word:
        if not check:
            check.append(w)
        else:
            if check[-1] == w:
                check.pop()
            else:
                check.append(w)
    if not check:
        result += 1
    test_case -= 1
print(result)