Week 2-1. [Hash Table] 242. Valid Anagram (Python3)

문제 해결 과정

✍️ 나만의 방식으로 문제 정리하기 (=체계화)

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

Valid Anagram - LeetCode

s와 t 두 개의 문자열이 주어질 때, t가 s의 anagram이라면 True, 아니면 False를 반환하라.

• | s, t | ∈ [1, 5*10^4]
• 두 문자열의 요소와 빈도수가 정확히 일치하면서 순서만 다르다면 anagram이라고 한다.

 

🔎 어떤 식으로 접근했는가?

이전 문제에서 활용한 Counter 함수를 이용했다.

 

🙈 알고리즘 선택: 입력의 크기를 바탕으로

Counter 함수는 내부적으로 linear search이다.

 

📝 의사 코드

s의 빈도수와 t의 빈도수가 같다면 True를 반환한다.

 

🎯 구현 코드

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

 

내 코드를 탐구해보기

⏱ 성능 측정 (시간복잡도/공간복잡도)

Counter 함수를 호출했을 때 각 문자열의 길이만큼 문자를 순회한다. 따라서 시간 복잡도는 O(n)이다.

 

✍️ 성능 회고

1초 제한에서 O(n)의 최대 입력은 10^6이다. 문제에서는 최대 입력이 5*10^4이므로 성능은 괜찮다.

 

다른 사람의 코드를 탐구해보기

🎯 구현 코드

두 문자열을 정렬했을 때 완전히 동일하다면, anagram이다.

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

 

⏱ 성능 측정 (시간복잡도/공간복잡도)

정렬 연사의 시간복잡도에 의해 결정된다. 정렬 연산의 시간복잡도는 최소 O(n log n)이다.

 

느낀 점

바로 이전에 풀었던 문제에서 알게된 Counter 함수를 이용하여 간단하게 풀 수 있었다.

 

만약 Counter 함수를 이용하지 않으려면,

딕셔너리를 이용해 각 알파벳의 개수를 카운트한 뒤, 두 문자열이 정확히 일치하는지 여부로 해결할 수 있었을 것이다.