[BOJ] 3986: 좋은 단어

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

 

 

 

 

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

int n, result;
string ab;
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n;
  for (int i = 0; i < n; i++) {
    stack<char> word;
    cin >> ab;
    for (char c : ab) {
      if (!word.empty() && word.top() == c)
        word.pop();
      else
        word.push(c);
    }
    if (word.empty()) result++;
  }
  cout << result << '\n';
}

이 문제를 보자마자 올바른 괄호쌍 판별 문제가 생각났다.

열린 괄호, 닫힌 괄호가 A, B라는 문자로 대체된 것뿐이지 문제의 근본은 똑같다.

따라서 괄호쌍 문제처럼 스택으로 금방 해결할 수 있다고 생각했다.

 

n에는 테스트 케이스를 입력받고, ab는 그다음 주어진 AB문자열을 받는다.

이제 ab문자열에서 문자를 하나씩 꺼내와서 스택의 pop과 push를 결정하면 된다.

 

스택이 empty면 무조건 push한다.

스택이 empty가 아니면 두 가지의 선택지가 있다.

스택의 top과 c가 같다면 동일한 쌍이므로 word.pop()을 실행한다.

반대로 스택의 top과 c가 같지 않다면 동일한 쌍이 아니므로 word.push()를 실행한다.

 

위 과정을 반복하고 마지막에 스택이 empty라면 모든 AB의 쌍이 올바른 것이고,

empty가 아니라면 올바른 쌍이 아니라는 것이다.