C++에서 문자 삭제 없이 두 문자열을 아나그램으로 만드는 최소 변경 횟수 구하기

같은 길이를 가진 두 개의 문자열이 있을 때, 어떤 문자도 삭제하지 않으면서 두 문자열을 아나그램(Anagram)으로 만들기 위해 필요한 최소 변경 횟수를 구하는 문제입니다. 아나그램이란 두 문자열이 동일한 문자 집합을 가지는 경우를 말합니다.

예를 들어 "HELLO"와 "WORLD"라는 두 문자열이 있다고 가정해 보겠습니다. 이 경우 세 글자가 서로 다르므로 필요한 변경 횟수는 3이 됩니다.

알고리즘 접근 방식

핵심 아이디어는 간단합니다. 먼저 첫 번째 문자열에서 각 문자의 빈도수(frequency)를 계산합니다. 그다음 두 번째 문자열을 순회하면서 해당 문자가 빈도 배열에 존재하면 빈도 값을 감소시킵니다. 만약 빈도 값이 0보다 작아지면, 이는 첫 번째 문자열에 없는 문자가 두 번째 문자열에 더 많다는 의미이므로 최종 카운트를 1 증가시킵니다.

즉, 두 문자열 간의 문자 빈도 차이를 통해 몇 개의 문자를 바꿔야 하는지 정확히 파악할 수 있습니다.

C++ 코드 예제

#include <iostream>
using namespace std;

int countAlteration(string str1, string str2) {
    int count = 0;
    int frequency[26];
    // 빈도 배열 초기화
    for (int i = 0; i < 26; i++) {
        frequency[i] = 0;
    }
    // 첫 번째 문자열의 각 문자 빈도 계산
    for (int i = 0; i < str1.length(); i++)
        frequency[str1[i] - 'A']++;
    // 두 번째 문자열을 순회하며 빈도 비교
    for (int i = 0; i < str2.length(); i++) {
        frequency[str2[i] - 'A']--;
        if (frequency[str2[i] - 'A'] < 0)
            count++;
    }
    return count;
}

int main() {
    string s1 = "HELLO", s2 = "WORLD";
    cout << "Number of required alteration: " << countAlteration(s1, s2);
}

실행 결과

Number of required alteration: 3

코드 설명

위 코드는 알파벳 대문자만을 다룬다고 가정하고 크기 26의 정수 배열을 사용합니다. 시간 복잡도는 O(n)으로, 문자열의 길이에 비례하여 선형적으로 실행됩니다.

첫 번째 반복문: str1의 각 문자에 대해 해당 인덱스(str1[i] - 'A')의 빈도를 증가시킵니다.
두 번째 반복문: str2의 각 문자에 대해 빈도를 감소시키고, 음수가 되면 str1에는 부족한 문자가 있다는 뜻이므로 count를 증가시킵니다.
결과: HELLO와 WORLD를 비교하면 H→W, L→R, O→D 총 3번의 변경이 필요하므로 3이 출력됩니다.