[알고리즘/Python] 242. Valid Anagram

📑 1. 문제 이해

https://leetcode.com/problems/valid-anagram/?envType=study-plan-v2&envId=top-interview-150 

Valid Anagram - LeetCode

 이 문제는 두 문자열이 Anagram이 되는지 확인하는 것입니다.  즉. 두 문자열의 사용한 문자의 종료와 그 갯수가 일치하는지 확인하는 것입니다. 

- 문자열을 빈 문자열일 수 없고, 영문자 소문자만 포함한다.

- 두 문자열의 길이가 다를 수도 있다. 

☑️ 테스트케이스

문제에서 주어진 테스트케이스는 다음과 같습니다.

 

Example1: s= "anagram", t="nagaram"

Example2: s= "rat", t = "car"

 

다음과 같은 케이스를 주의해야합니다.

s= "abc" t = "a"

   - 두 문자열의 길이가 다르다. s가 t보다 길다.

s= "a" t = "abc"

   - 두 문자열의 길이가 다르다.

💡 2. 알고리즘 설계 - 딕셔너리

 두 문자열의 문자 구성을 살펴봐야합니다. 딕셔너리에 {문자: 카운트} 쌍을 저장한후 그 값이 t문자열과 같은지 확인합니다. 각 문자의 등장횟수를 딕셔너리에 저장하면 O(1)시간에 등장횟수를 불러올 수 있습니다.  

 이때 두 문자열의 길이가 다른 경우를 주의해야 합니다. 만약 따로 검사를 하지 않는다면 s가 t를 포함하는 경우에 True가 반환될 수 있기 때문입니다.

 

1. s와 t의 길이가 같지 않다면 Anagram이 될 수 없으므로 False를 반환한다.

2. s의 문자열을 순회하며 {값: 등장횟수} 형태로 저장한다.

3. t를 문자열을 순회하며 등장횟수를 1을 감소시킨다. 만약 t의 문자 c가 d에 존재하지 않거나, 0보다 작으면 문자c가 s보다 t에 더 많이 존재한다는 의미이므로 False를 반환한다.

4. 반복문이 끝나면 두 문자열의 문자 구성이 같은 것으로 True를 반환한다.

    def isAnagram2(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False

        d = dict()
        for c in s:
            d[c] = d.get(c, 0) + 1

        for c in t:
            if c in d and d[c] > 0:
                d[c] -= 1
            else:
                return False
        return True

시간 복잡도 및 공간 복잡도

시간 복잡도: O(N). 두 문자열을 각각 한번씩 순회해야한다. 두 문자열의 길이의 합을 N이라고 하면 시간복잡도는 O(N)이 된다.

공간 복잡도: O(N). s의 문자구성을 저장할 딕셔너리가 필요하다. s의 모든 문자가 다를 경우에 딕셔너리는 s의 길이만큼의 key값을 가진다.

 

⚒️ 3. 최적화 - Counter 사용

python이 제공하는 Counter를 사용해서 최적화할 수 있습니다. python이 제공하는 모듈로 내부적으로 최적화되어 있어 빠른 시간에 수행할 수 있습니다. 또한 길이가 다른 경우를 따로 처리해주지 않아도 됩니다. 

   def isAnagram(self, s: str, t: str) -> bool:
        sCounter = Counter(s)
        tCounter = Counter(t)
        return sCounter == tCounter

시간 복잡도 및 공간 복잡도

시간 복잡도: O(N). Counter 내부적으로 두 문자열을 각각 한번씩 순회해야한다. 두 문자열의 길이의 합을 N이라고 하면 시간복잡도는 O(N)이 된다.

공간 복잡도: O(N). s와 t의 문자구성을 저장할 딕셔너리가 필요하다.

 

 ⎌ 4. 검토

앞에서 살펴본 테스트 케이스들을 검토해보면 다음과 같습니다.

 

Example1: s= "anagram", t="nagaram"

Example2: s= "rat", t = "car"

   -> counter에 저장된 값이 같으므로 True가 반환됩니다.

 

s= "abc" t = "a"

s= "a" t = "abc"

   -> 두 문자열의 길이가 다른 경우에 counter에 저장된 값이 다르므로 False가 반환됩니다.

---

🤔 다른 사람의 풀이

이 외에도 1) 정렬한 결과가 같은지 살펴보기- O(NlogN) 2)알파벳을 나타내는 26길이의 배열을 만들고 각 칸에 몇번 등장하는지 기록하는 방법 O(N)등이 있습니다.

---

✅ 정리

◎ 원소의 개수를 셀 때는 Counter를 사용할 수 있다. 하지만 이는 dictionary를 확장한 것으로 내부적으로 순서가 없다는 것을 주의해야한다,.

◎ 직접 딕셔너리를 만들어서 비교하는 경우 두 문자열의 길이가 다를때 문제가 생길 수 있다.