[알고리즘, Python] 두 문자열이 아나그램 (Anagram)인지 확인하기

이전에 정렬 및 탐색을 공부할 때 아나그램끼리 묶는 문제를 풀었다.

[알고리즘, Python] 아나그램(Anagram) 묶기

이번에는 단순히 두 문자열이 주어지고 둘이 아나그램인지 확인하는 문제를 풀 것이다.

 

* leecode에서 문제 보기

https://leetcode.com/problems/valid-anagram/

Valid Anagram - LeetCode

---

우선 가장 먼저 생각난 방법은 해시맵을 사용하는 방법이었다.

 

문자열은 소문자의 영문으로만 주어져있다는 조건이 없었으면 키 값을 ASCII 코드로 해결했을것 같은데, 이 문제에서는 그냥 알파벳 그대로 키 값으로 사용하겠다.

 

문제를 살펴봤을 때 문자열 s와 t가 반드시 같은 길이라는 조건은 없다. 그러므로 두 문자열의 길이를 체크하고 다를 경우 False를 리턴한다.

 

그 다음으로는 문자열 s를 순회하며 각 문자열의 개수를 해시맵에 더해주고, 두번째 문자열 t를 순회하며 발견되는 문자열을 해시맵에서 하나씩 빼준다.

 

만약 두 문자열이 아나그램이라면 모든 해시맵의 value는 0이 될 것이다.

 

이런 논리로 작성한 코드는 아래와 같다.

def isAnagram(s, t):
    if len(s) != len(t):
        return False

    hm = {}
    for char in s:
        if char in hm:
            hm[char] += 1
        else:
            hm[char] = 1

    for char in t:
        if char in hm:
            hm[char] -= 1
        else:
            return False

    return True if len(set(hm.values())) == 1 else False

 

시간복잡도는 O(n)이 될 것이다.

하지만 리트코드 실행 결과 런타임이 그닥 좋지 않다. 그래서 더 좋은 방법이 있나 discuss에서 다른 사람들의 솔루션을 확인해봤다. 그 중 한줄로 99.15%를 달성했다는 사람의 코드를 봤다.

https://leetcode.com/problems/valid-anagram/discuss/66654/Python-one-line-beats-99.15

all(s.count(x) == t.count(x) for x in 'abcdefghijklmnopqrstuvwxzy')

즉 문제에서 소문자 알파벳으로만 이루어졌다고 했으므로, 두 문자열 s와 t가 a에서 z 사이의 알파벳을 몇 개 가지고 있는지 count하고 모두 같은 경우 아나그램이라도 판단하는 코드다.

 

이 외에도 s와 t를 정렬해서 비교하는 것도 하나의 방법이 될 수 있겠지만 위 두가지 방법보다 성능이 낮을 것으로 예상되니 구현하지는 않았다.

---

출처

모든 출처는 본문에 포함되어 있습니다.