[LeetCode] 242. Valid Anagram - Python

 

 

Disclaimer: 배워가면서 정리하고 있습니다. 개념에 오류가 있을 수 있습니다.

1. 문제 살펴보기

• 문제로 이동:
  Valid Anagram

문제 해설

• 문자열로 된 두 변수 s와 t가 주어진다.
• t가 s의 애너그램*이면 True를 반환하고 그렇지 않으면 False를 반환한다.

제약사항

• s, t는 모두 소문자로 이루어진 단어라고 가정한다.
• s와 t는 5* 10^4 보다 작은 철자로 이루어진 단어라고 가정한다.

*애너그램은 어구전철이라고도 불린다. 한 글자의 철자를 재배열 하여 다른 단어를 만드는 것을 말한다.

예시

2. 답을 도출하는 방법

문자열 정렬 방식

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        return sorted(s) == sorted(t)

장점

• 코드 간결, 한줄에 문제를 풀 수 있음
• 문자열에 어떤 문자가 나오든 상관없이 확실히 작동함

단점

• 시간복잡도가 O(nlogn)으로 매우 긴 문자열일때는 비효율적임.
• 정렬 과정에서 메모리를 별도로 사용함.
• 코드 자체는 짧지만 메모리와 시간복잡도를 생각했을 때 최적화된 방법은 아님.

해시테이블

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t): 
            return False 
            # 두 수가 가진 알파벳의 숫자가 다르면 애너그램일 수 없음

        hashmap = {}
        for char in s: 
            hashmap[char] = hashmap.get(char, 0) + 1 
            # .get을 사용해 0이라는 디폴트 값을 정해주지 않으면, 
            # 해당 알파벳이 hashmap에 없을 경우 +1을 할 단어가 없어서 오류가 발생함. 
        for char in t:
            if char not in hashmap or hashmap[char] == 0:
                return False 
            hashmap[char] -= 1
        return True

장점

• 시간 복잡도가 O(n)이고 한번씩만 순회하면 됨.
• 유니코드 등 영어 소문자 이외의 다양한 문자에도 적용 가능.

단점

• 해시 테이블이 공간 메모리를 차지.
• 코드가 장황해보임.

알파벳 배열 방식

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False 
        count = [0] * 26 
        for a, b in zip(s, t):
            count[ord(a) - ord('a')] += 1
            count[ord(b) - ord('a')] -= 1
        # ord 함수는 하나의 문자를 받아서, 문자에 해당하는 유니코드 값을 정수로 반환하는 내장 함수
        # 알파벳 문자를 0-25의 인덱스 값으로 변환하여 배열에서 바로 색인 
        return all(x == 0 for x in count)

장점

• 소문자 알파벳 한정, 공간 복잡도가 O(1)으로 매우 효율적임
• 실행 속도 매우 빠름. 심플한 배열 연산으로 처리됨

단점

• 소문자 영어 의외의 다른 문자는 처리 할 수 없음
• (이 문제의 경우, 단어가 소문자 영어라고 가정하기 때문에 사용 가능)

Counter 라이브러리 사용

from collections import Counter

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

장점

• 파이썬 내장 라이브러리 Counter를 사용하여 매우 간결하게 작성 가능.
• 코드가 간결하고 비교가 매우 빠르며 복잡한 로직을 만들 필요가 없음.

단점

• Counter등 외부 라이브러리 사용이 제한된 환경에서는 쓸 수 없음.
• 내부적으로 딕서너리 기반 카운팅을 하기 때문에(라이브러리 안에서) 공간을 실질적으로는 더 사용함.

3. 시간복잡도 및 공간복잡도 비교

풀이 방식	시간 복잡도	공간 복잡도
정렬 방식	O(n log n)	O(n)
해시 테이블 방식	O(n)	O(n)
Counter 활용	O(n)	O(n)
알파벳 배열 방식	O(n)	O(1)

4. 참고자료

Algo Engine

 

NeetCode