[백준] 3986번: 좋은 단어 C++로 풀어보기

3986번 설명

어떻게 풀까? (문제를 처음 보고 든 생각)

스택을 사용하자.

for문을 써서 현재 for문이 가리키는 알파벳이 스택의 top에 있는 알파벳과 같다면 pop을 하자.

for문 loop가 다 끝나고 스택이 비어있으면 좋은 단어고, 아니면 좋은 단어가 아니다.

 

코드

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


int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n; // 단어 수
	int cnt = 0; // 좋은 단어 개수
	cin >> n;


	while (n--) {

		stack <char> s;
		string a;
		cin >> a;

		for (int i = 0; i < a.length(); i++) {
			if (s.empty()) { // 스택이 비어있다면
				s.push(a[i]); // 현재 알파벳 push
			}
			else if(s.top() == a[i]){ // 스택의 top과 현재 알파벳이 같다면
				s.pop(); // pop!
			}
			else {
				s.push(a[i]); // 아니라면 현재 알파벳을 스택에 push
			}
		}

		if (s.empty()) { // 만약 스택이 비어있다면
			cnt++; // cnt를 더해준다.
		}
	}

	cout << cnt; // cnt 출력
}

 

결과

3986번 결과

왜 이렇게 많이 틀렸냐면...

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

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	stack <char> s;
	int n;
	int cnt = 0;
	string a;
	cin >> n;


	while (n--) {

		while (!s.empty()) { // 스택이 비어있지 않다면
			s.pop(); // 비워준다.
		}

		cin >> a;

		for (int i = 0; i < a.length(); i++) {
			if (s.empty()) { // 만약 스택이 비어있으면
				s.push(a[i]); // 현재 알파벳을 스택에 푸쉬
			}
			else if (s.top() == 'A') { // 만약 스택의 top이 'A'라면
				if (a[i] == 'A') { // 그리고 현재 알파벳이 'A'라면
					s.pop(); // 스택을 pop 한다.
				}
			}
			else if (s.top() == 'B') { // 만약 스택의 top이 'B'라면
				if (a[i] == 'B') { // 그리고 현재 알파벳이 'B'라면
					s.pop(); // 스택을 pop 한다.
				}

			}
			else {
				s.push(a[i]);
			}
		}

		if (s.empty()) {
			cnt++;
		}
	}

	cout << cnt;
}

이것도 논리상으로는 다 맞는 거 같은데 틀렸다고해서 여기저기 건들다가 저 사단이 났다.

왜 틀린 걸까? 계속 생각해봐야겠다.