BOJ 3778 - 애너그램 거리

문제

두 문자열이 주어질 때, 한 문자열을 다른 문자열의 애너그램으로 만들기 위해 추가하거나 삭제해야 하는 문자의 최소 개수(애너그램 거리)를 구하라.

입력

테스트 케이스 수 T, 각 케이스마다 소문자로 이루어진 두 문자열이 주어진다.

출력

각 테스트 케이스마다 "Case #i: 거리"를 출력한다.

예제

입력	출력
`1` `asdf` `aaas`	`Case #1: 6`

풀이

알파벳 빈도 배열을 이용하여 두 문자열의 문자 차이를 계산한다.

크기 26의 빈도 배열을 0으로 초기화한다
첫 번째 문자열의 각 문자에 대해 해당 알파벳 카운트를 증가시킨다
두 번째 문자열의 각 문자에 대해 해당 알파벳 카운트를 감소시킨다
26개 알파벳에 대해 빈도 차이의 절댓값을 모두 합산한다

핵심 아이디어: 빈도 배열의 양수 값은 삭제해야 할 문자, 음수 값은 추가해야 할 문자를 의미하므로, 절댓값 합이 곧 애너그램 거리가 된다.

코드

#include <iostream>
using namespace std;
 
int main()
{
  cin.tie(NULL);
  cin.sync_with_stdio(false);
  int t;
  cin >> t;
  cin.ignore();
  for (int c = 1; c <= t; ++c)
  {
    char cnt[26] = {};
    char a[50], b[50];
    cin.getline(a, 100);
    cin.getline(b, 100);
    int ret = 0;
 
    for (int i = 0; a[i]; ++i)
    {
      ++cnt[a[i] - 'a'];
    }
 
    for (int i = 0; b[i]; ++i)
    {
      --cnt[b[i] - 'a'];
    }
 
    for (int i = 0; i < 26; ++i)
    {
      ret += cnt[i] < 0 ? -cnt[i] : cnt[i];
    }
    cout << "Case #" << c << ": " << ret << '\n';
  }
}

복잡도

시간: O(T * (N + M)) (T: 테스트 케이스 수, N, M: 각 문자열 길이)
공간: O(1)

문제