[백준 11608] Complexity (C#, C++) - soo:bak

문제 링크

11608번 - Complexity

설명

문자열에서 서로 다른 글자가 많을 때, 글자를 지워서 서로 다른 글자가 두 개 이하가 되도록 하는 문제입니다.

접근법

지우지 않을 글자를 최대 두 종류까지 고를 수 있습니다.

따라서 각 글자의 등장 횟수를 세고, 가장 많이 나온 두 글자를 남기는 것이 삭제 횟수를 최소로 합니다.

전체 길이에서 두 글자의 개수를 뺀 값이 필요한 최소 삭제 횟수입니다.

---

Code

C#

using System;

class Program {
  static void Main() {
    var s = Console.ReadLine()!;
    var cnt = new int[26];
    foreach (var ch in s)
      cnt[ch - 'a']++;

    var top1 = 0;
    var top2 = 0;
    for (var i = 0; i < 26; i++) {
      var v = cnt[i];
      if (v > top1) { top2 = top1; top1 = v; }
      else if (v > top2) top2 = v;
    }

    var ans = s.Length - (top1 + top2);
    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 ch : s)
    cnt[ch - 'a']++;

  int top1 = 0, top2 = 0;
  for (int i = 0; i < 26; i++) {
    int v = cnt[i];
    if (v > top1) { top2 = top1; top1 = v; }
    else if (v > top2) top2 = v;
  }

  int ans = (int)s.size() - (top1 + top2);
  cout << ans << "\n";

  return 0;
}