[백준 3986/C++] 좋은 단어

1. 문제

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

3986번: 좋은 단어

---

2. 문제 풀이

#include <iostream>
#include <bits/stdc++.h>
#pragma warning (disable:4996)

using namespace std;

int ans;

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n; cin >> n;
	while (n--) {
		stack<int> stk;
		string s; cin >> s;
		for (int i = 0; i < s.size(); i++) {
			if (stk.empty())
				stk.push(s[i]);
			else if (stk.top() == s[i])
				stk.pop();
			else
				stk.push(s[i]);
		}
		if (stk.empty())
			ans++;
	}
	cout << ans;
}

---

2. 문제 평가 및 해설

스택을 이용한 간단한 문제이다.

스택, 큐 그리고 덱은 크게 두 가지 유형이 있는 것 같다.

1. 쌓아가면서 비교하기

2. 일단 먼저 쌓고, 비교하기

이번 문제의 경우는 전자이다. 문제 풀이는 다음과 같다.

1. 문자열을 받고, 스택을 쌓아가면서 스택의 top과 문자열을 비교하면서 나아가면 된다.

2. 스택의 top과 문자가 일치한다면, 스택을 pop하고, 그렇지 않다면 push 해준다.

3. 여기서 주의해야할 점은 for문에서 문자열을 처음 비교할 때, 스택이 비워져있으므로 stk.top()을 실행한다면 런타임 에러가 발생한다. 자료구조와 관련된 문제를 풀 때 가장 중요한 부분이다.

 4. 마지막으로, 스택이 비워있다면 좋은 단어이므로 ans++을 해준다.