[백준 3986] 좋은 단어 (C#, C++) - soo:bak

문제 링크

3986번 - 좋은 단어

설명

A와 B로만 이루어진 단어가 주어질 때, 같은 글자끼리 교차하지 않게 짝지어 모든 글자를 정확히 한 번씩 짝지을 수 있는지 판별하는 문제입니다.

접근법

문자를 왼쪽부터 하나씩 보면서 스택을 사용합니다.

현재 글자가 스택의 맨 위와 같으면 두 글자를 짝지을 수 있으므로 스택에서 꺼냅니다. 다르면 아직 짝을 찾지 못한 글자이므로 스택에 넣습니다.

이 과정을 끝까지 했을 때 스택이 비어 있으면 모든 글자가 짝지어진 것이고, 비어 있지 않으면 남는 글자가 있으므로 좋은 단어가 아닙니다.

각 단어마다 이 판정을 수행해 좋은 단어의 개수를 세면 됩니다.

---

Code

C#

using System;

class Program {
  static void Main() {
    int n = int.Parse(Console.ReadLine()!);
    int answer = 0;

    for (int t = 0; t < n; t++) {
      string word = Console.ReadLine()!;
      char[] stack = new char[word.Length];
      int top = 0;

      foreach (char ch in word) {
        if (top > 0 && stack[top - 1] == ch)
          top--;
        else
          stack[top++] = ch;
      }

      if (top == 0)
        answer++;
    }

    Console.WriteLine(answer);
  }
}

C++

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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n;
  cin >> n;

  int answer = 0;

  while (n--) {
    string word;
    cin >> word;

    vector<char> st;
    for (char ch : word) {
      if (!st.empty() && st.back() == ch)
        st.pop_back();
      else
        st.push_back(ch);
    }

    if (st.empty())
      answer++;
  }

  cout << answer << "\n";

  return 0;
}