[백준 11195] Peragrams (C#, C++) - soo:bak

문제 링크

11195번 - Peragrams

설명

주어진 문자열에서 문자를 제거해 어떤 팰린드롬의 애너그램이 되도록 할 때 최소 제거 수를 구하는 문제입니다.

접근법

먼저 각 문자의 등장 횟수를 센 뒤 홀수 개의 문자가 몇 종류인지 확인합니다.

다음으로 팰린드롬이 되려면 홀수 개수인 문자는 한 종류만 남을 수 있으므로, 나머지 홀수 개수들은 한 글자씩 제거해야 합니다.

마지막으로 홀수 종류 수에서 1을 뺀 값이 최소 제거 수가 됩니다.

---

Code

C#

using System;

class Program {
  static void Main() {
    var s = Console.ReadLine()!;
    var cnt = new int[26];
    for (var i = 0; i < s.Length; i++) {
      cnt[s[i] - 'a']++;
    }

    var odd = 0;
    for (var i = 0; i < 26; i++) {
      if (cnt[i] % 2 == 1) odd++;
    }

    var ans = odd == 0 ? 0 : odd - 1;
    Console.WriteLine(ans);
  }
}

C++

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

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

  string s; cin >> s;

  int cnt[26] = {};
  for (char c : s) cnt[c - 'a']++;

  int odd = 0;
  for (int i = 0; i < 26; i++) {
    if (cnt[i] % 2 == 1) odd++;
  }

  int ans = odd == 0 ? 0 : odd - 1;
  cout << ans << "\n";

  return 0;
}