C++로 문자열 배열의 모든 아나그램 쌍 찾아 출력하기

이 문제에서는 문자열 배열이 주어지며, 해당 배열에 포함된 모든 아나그램 쌍을 찾아 출력해야 합니다.

아나그램(Anagram)은 한 문자열의 문자들을 재배열하여 만들 수 있는 다른 문자열을 의미합니다. 예를 들어 'hello'와 'lolhe'는 서로 아나그램 관계입니다.

문제를 더 잘 이해하기 위해 예시를 살펴보겠습니다.

입력: array = {"hello", "hrdef", "from", "lohel", "morf"}
출력: [hello, lohel], [from, morf]

접근 방법

이 문제는 중첩 반복문(nested loop)을 사용하여 해결할 수 있습니다. 두 개의 중첩 루프가 필요하며, 외부 루프는 배열을 순회하며 기준이 되는 문자열을 선택하고, 내부 루프는 나머지 문자열들과 비교하여 아나그램 여부를 검사합니다.

두 문자열이 아나그램인지 확인하는 방법은 각 문자의 출현 빈도를 세는 것입니다. 두 문자열의 길이가 같고, 모든 문자의 빈도가 동일하다면 두 문자열은 아나그램입니다.

예제 코드

위 알고리즘을 구현한 C++ 프로그램을 살펴보겠습니다.

#include <iostream>
using namespace std;
#define NO_OF_CHARS 256
bool isAnagramString(string str1, string str2){
   int count[NO_OF_CHARS] = {0};
   int i;
   for (i = 0; str1[i] && str2[i]; i++){
      count[str1[i]]++;
      count[str2[i]]--;
   }
   if (str1[i] || str2[i])
      return false;
   for (i = 0; i < NO_OF_CHARS; i++)
      if (count[i])
         return false;
      return true;
}
void printAnagrams(string arr[], int n){
   for (int i = 0; i < n; i++)
      for (int j = i+1; j < n; j++)
         if (isAnagramString(arr[i], arr[j]))
            cout<<arr[i]<<" and "<<arr[j]<<" are anagrams.\n";
}
int main(){
   string arr[] = {"hello", "hrdef", "from", "lohel", "morf"};
   int n = sizeof(arr)/sizeof(arr[0]);
   printAnagrams(arr, n);
   return 0;
}

실행 결과

hello and lohel are anagrams.
from and morf are anagrams.

효율성 개선 방법

위 방법은 이해하기 쉽다는 장점이 있지만, 시간 복잡도가 O(n² × L)로 비교적 비효율적입니다. 따라서 성능을 개선하기 위해 몇 가지 최적화를 적용할 수 있습니다.

대표적인 최적화 방법은 배열에 있는 각 문자열의 문자들을 정렬한 뒤, 정렬된 결과를 해시 맵(hash map)에 키로 저장하는 것입니다. 아나그램은 정렬하면 항상 같은 문자열이 되므로, 같은 키를 가진 문자열들을 그룹으로 묶으면 한 번의 순회만으로 모든 아나그램 그룹을 찾을 수 있습니다. 이렇게 하면 시간 복잡도를 O(n × L log L)까지 줄일 수 있어 대량의 데이터에서도 훨씬 효율적으로 동작합니다.