[백준 14043] Ragaman (C#, C++) - soo:bak

문제 링크

14043번 - Ragaman

설명

첫 번째 문자열의 애너그램에서 일부 문자를 *로 바꾼 것이 두 번째 문자열이 될 수 있는지 판별하는 문제입니다.

접근법

첫 번째 문자열의 각 알파벳 개수를 셉니다. 그 다음 두 번째 문자열을 보면서 알파벳은 개수를 하나씩 빼고, *는 따로 개수를 셉니다.

두 번째 문자열에 나온 알파벳 때문에 어떤 문자의 개수가 음수가 되면, 첫 번째 문자열보다 더 많이 사용한 문자가 있다는 뜻이므로 바로 불가능합니다.

끝까지 처리한 뒤 아직 남아 있는 문자 개수의 합이 *의 개수와 같으면, 그 부족한 부분을 모두 *로 채울 수 있으므로 가능한 경우입니다. 아니면 불가능합니다.

---

Code

C#

using System;

class Program {
  static void Main() {
    string a = Console.ReadLine()!;
    string b = Console.ReadLine()!;

    int[] count = new int[26];
    foreach (char ch in a)
      count[ch - 'a']++;

    int star = 0;
    foreach (char ch in b) {
      if (ch == '*') {
        star++;
      } else {
        count[ch - 'a']--;
        if (count[ch - 'a'] < 0) {
          Console.WriteLine("N");
          return;
        }
      }
    }

    int remain = 0;
    for (int i = 0; i < 26; i++)
      remain += count[i];

    Console.WriteLine(remain == star ? "A" : "N");
  }
}

C++

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

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

  string a, b;
  cin >> a >> b;

  vector<int> count(26, 0);
  for (char ch : a)
    count[ch - 'a']++;

  int star = 0;
  for (char ch : b) {
    if (ch == '*') {
      star++;
    } else {
      count[ch - 'a']--;
      if (count[ch - 'a'] < 0) {
        cout << "N\n";
        return 0;
      }
    }
  }

  int remain = 0;
  for (int i = 0; i < 26; i++)
    remain += count[i];

  cout << (remain == star ? "A" : "N") << "\n";

  return 0;
}