anagrams을 검증하는 방법(Check if Two Strings Are Anagrams in Java)

원본 글: https://www.baeldung.com/java-strings-anagrams

anagram은 주어진 단어나 문장에서 글자들을 재배열해서 다른 단어나 문장을 만드는 것을 말합니다.

예를 들어, "listen"이라는 단어는 "silent"라는 단어의 아나그램입니다. 글자의 순서만 바뀌었고, 사용된 글자들의 개수는 똑같죠.

각 문자의 개수와 종류가 정확히 같으면 아나그램이라고 할 수 있습니다.

이러한 단어를 검증하는 방법을 학습합니다.

1. Solution

두 문자열이 anagram인지 확인하는 몇 가지 방법을 비교해봅니다.

먼저 두 문자열의 길이가 같은지 확인합니다. 문자열의 길이가 서로 다르면 angram이 될 수 없기 때문입니다.

2. Check by Sorting

문자를 정렬하고 정렬된 문자를 비교하면 anagram인지 확인이 가능합니다.

@Test
public void java_core_anagram() {
    Assertions.assertTrue(isAnagramSort("!low-salt!", "owls-lat!!"));
}

public static boolean isAnagramSort(String string1, String string2) {
    if(string1.length() != string2.length()){
        return false;
    }

    char[] a1 = string1.toCharArray();
    char[] a2 = string2.toCharArray();

    Arrays.sort(a1);
    Arrays.sort(a2);
    return Arrays.equals(a1, a2);
}

위 코드는 이해하기 쉽지만 시간복잡도가 O(n log n)으로 큽니다. 정렬하는 sort() 함수가 O(n log n) 시간복잡도를 가지고 있기 때문입니다. 그리고 추가 메모리를 사용하여 배열을 새로 만들기에 이부분에 대한 고려도 필요합니다.

3. Check by Counting

대체 전략으로는 각 문자열에 포함된 문자의 발생 횟수를 세는 방법이 있습니다.

만약 이 히스토그램(각 문자에 대한 카운트)이 두 문자열에서 동일하다면, 두 문자열은 아나그램입니다.

조금 더 메모리를 절약하기 위해, 하나의 히스토그램만 만들 수 있습니다.

첫 번째 문자열의 각 문자를 만나면 그 카운트를 증가시키고, 두 번째 문자열의 각 문자를 만나면 그 카운트를 감소시킵니다.

만약 두 문자열이 아나그램이라면, 모든 카운트가 0으로 균형을 이루게 됩니다.

이 히스토그램은 문자 집합 크기에 의해 정의된 고정 크기의 카운트 테이블이 필요합니다. 예를 들어, 각 문자를 저장하는 데 1바이트만 사용한다면, 각 문자의 발생 횟수를 세기 위해 크기가 256인 배열을 사용할 수 있습니다.

private static int CHARACTER_RANGE= 256;

@Test
public void use_histogram_anagram_test() {
    Assertions.assertTrue(isAnagramCounting("!low-salt!", "owls-lat!!"));
}

public static boolean isAnagramCounting(String string1, String string2) {
    if(string1.length() != string2.length()){
        return false;
    }

    int count[] = new int[CHARACTER_RANGE];
    for(int i = 0; i< string1.length(); ++i) {
        count[string1.charAt(i)]++;
        count[string2.charAt(i)]--;
    }

    for(int i = 0; i< CHARACTER_RANGE; ++i) {
        if(count[i] != 0){
            return false;
        }
    }
    return true;
}

시간복잡도는 O(n)으로 위보다는 빠릅니다. 하지만 문자 갯수를 세기위한 추가적인 공간이 필요하며 ASCII코드를 벗어난 문자에 대해서는 위에서 쓰인 256바이트의 공간보다 더 쓰일 수 있습니다.

4. Check with MultiSet

Multset이라는 자료구조를 통해서 좀 더 간편하게 비교할 수 있습니다.

Multset은 순서와 상관없이 중복을 지원하는 자료구조입니다. 예를 들어, 멀티셋 {a, a, b}와 {a, b, a}는 순서는 다르지만 동일하다고 간주됩니다.

이를 사용하기 위해서는 guava라는 라이브러리가 필요합니다.

testImplementation 'com.google.guava:guava:32.1.3-jre'

@Test
public void use_multiset_anagram_test() {
    Assertions.assertTrue(isAnagramMultiset("!low-salt!", "owls-lat!!"));
}

public static boolean isAnagramMultiset(String string1, String string2) {
    if(string1.length() != string2.length()){
        return false;
    }

    Multiset<Character> multiset1 = HashMultiset.create();
    Multiset<Character> multiset2 = HashMultiset.create();

    for(int i =0; i<string1.length(); ++i) {
        multiset1.add(string1.charAt(i));
        multiset2.add(string2.charAt(i));
    }
    return multiset1.equals(multiset2);
}

문자열 하나를 잡고 길이만큼 순회하면서 MultiSet에 넣고 비교합니다.

장점은 추가 메모리공간이 필요없고 O(n)으로 동작한다는점입니다. 이전 방식과 비슷하지만 가변 길이의 MultiSet을 사용한다는점이 다릅니다.

5. Letter-based Anagram

지금까지의 예시들은 엄밀히 말하면 언어학적 정의에 맞는 아나그램이 아닙니다.

왜냐하면 문장 부호 문자를 아나그램의 일부로 간주하고 있으며, 대소문자를 구분하기 때문입니다.

이제 이를 수정하여 문자 기반의 아나그램을 고려해 보겠습니다.

공백이나 구두점 같은 다른 문자는 무시하고 대소문자를 구분하지 않고 문자만 재배열하는 방식으로 아나그램을 정의할 것입니다. 예를 들어, "A decimal point"와 "I’m a dot in place."는 서로 아나그램이 될 수 있습니다.

이 문제를 해결하기 위해 먼저 두 입력 문자열을 전처리하여 원하지 않는 문자를 필터링하고, 문자를 소문자로 변환합니다. 그런 다음 위에서 언급한 방법 중 하나(예: MultiSet 방법)를 사용하여 처리된 문자열에서 아나그램을 확인할 수 있습니다.

String preprocess(String source) {
    return source.replaceAll("[^a-zA-Z]", "").toLowerCase();
}

boolean isLetterBasedAnagramMultiset(String string1, String string2) {
    return isAnagramMultiset(preprocess(string1), preprocess(string2));
}

이 방법은 아나그램 문제를 해결하기 위한 보편적인 방법입니다. 숫자가 포함되어있어도 해당 방식을 통해 해결할 수 있습니다.

6. 결론

아나그램 문제를 해결하기 위한 세 가지 알고리즘을 학습하였습니다.

각 해결법은 시간복잡도나 공간복잡도 측면에서 장단점을 가지고 있습니다.

그리고 전통적으로 아나그램을 판별하기 위해서는 소문자로 변환하여 비교해야한다는 것도 확인하였습니다.

예제코드