Python으로 문자열 아나그램(Anagram) 여부 확인하기

아나그램(Anagram)은 주어진 문자열의 모든 순열(permutation)을 의미합니다. 일반적인 패턴 검색 알고리즘과 달리, 이 문제에서는 텍스트 안에서 정확한 패턴만 찾는 것이 아니라 주어진 패턴의 모든 가능한 배열을 검색해야 합니다.

예를 들어 "ANAGRAM"과 "NAAGARM"은 글자의 구성이 같으므로 서로 아나그램 관계입니다. 반면 "cat"과 "fat"은 구성하는 글자가 다르기 때문에 아나그램이 아닙니다.

문제 해결 접근 방식

두 문자열이 아나그램인지 판별하는 가장 간단하고 직관적인 방법은 다음과 같습니다.

각 문자열을 개별 문자들의 리스트로 변환합니다.
두 리스트를 각각 정렬(sort)합니다.
정렬된 결과가 완전히 동일하다면 두 문자열은 아나그램입니다.

정렬 후 비교하면 글자의 등장 순서와 무관하게 구성 요소만 비교할 수 있으므로, 아나그램 판별이 매우 쉬워집니다.

Python 구현 예제

아래 코드는 위 접근 방식을 Python으로 구현한 것입니다.

class Solution(object):
    def isAnagram(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """
        return "".join(sorted(s)) == "".join(sorted(t))

ob1 = Solution()
print(ob1.isAnagram("ANAGRAM", "NAAGARM"))

코드 설명

sorted(s): 문자열 s를 문자 단위로 정렬하여 리스트로 반환합니다.
"".join(...): 정렬된 문자 리스트를 다시 하나의 문자열로 합칩니다.
두 문자열의 정렬 결과가 같으면 True, 다르면 False를 반환합니다.

입력

s = "ANAGRAM"
t = "NAAGARM"

출력

true

마무리

이 방법은 구현이 간단하고 이해하기 쉽다는 장점이 있습니다. 시간 복잡도는 문자열 길이를 n이라 할 때 O(n log n)으로, 정렬에 의해 결정됩니다. 더 최적화가 필요하다면 각 문자의 출현 횟수를 세는 Counter(빈도수 계산) 방식을 사용해 O(n) 시간 복잡도로 개선할 수도 있습니다.