[백준 32560] Amalgram (C#, C++) - soo:bak

문제 링크

32560번 - Amalgram

설명

두 단어를 모두 포함할 수 있는 최소 길이 문자열을 만드는 문제입니다.

접근법

두 단어를 모두 부분 수열로 포함하려면, 각 알파벳이 두 단어 중 더 많이 등장하는 횟수만큼 있어야 합니다.

따라서 알파벳별로 두 단어의 등장 횟수 중 최댓값을 취해 그만큼 이어붙이면 최소 길이 문자열이 됩니다.

---

Code

C#

using System;
using System.Text;

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

    var ca = new int[26];
    var cb = new int[26];
    foreach (var ch in a)
      ca[ch - 'a']++;
    foreach (var ch in b)
      cb[ch - 'a']++;

    var total = 0;
    for (var i = 0; i < 26; i++)
      total += Math.Max(ca[i], cb[i]);

    var sb = new StringBuilder(total);
    for (var i = 0; i < 26; i++) {
      var cnt = Math.Max(ca[i], cb[i]);
      if (cnt > 0) sb.Append((char)('a' + i), cnt);
    }

    Console.WriteLine(sb.ToString());
  }
}

C++

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

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

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

  int ca[26] = {}, cb[26] = {};
  for (char ch : a)
    ca[ch - 'a']++;
  for (char ch : b)
    cb[ch - 'a']++;

  int total = 0;
  for (int i = 0; i < 26; i++)
    total += max(ca[i], cb[i]);

  string res;
  res.reserve(total);
  for (int i = 0; i < 26; i++) {
    int cnt = max(ca[i], cb[i]);
    if (cnt > 0) res.append((size_t)cnt, (char)('a' + i));
  }

  cout << res << "\n";

  return 0;
}