Valid Anagram

문제 링크

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

문제 설명

두 개의 문자열 s와 t가 주어질 때, 문자열 t가 문자열 s의 애너그램(anagram)인지 여부를 확인하는 함수를 작성하세요. 애너그램이란, 한 문자열의 문자를 재배열하여 다른 문자열을 만들 수 있는 경우를 의미합니다. 두 문자열이 애너그램이라면, 두 문자열은 동일한 문자로 구성되어 있어야 하며, 각 문자의 개수도 같아야 합니다.

예제

예제 1
- 입력: s = "anagram", t = "nagaram"
- 출력: true
예제 2
- 입력: s = "rat", t = "car"
- 출력: false

풀이 전략

애너그램을 확인하기 위해 다음과 같은 접근 방법을 사용할 수 있습니다.

문자 개수 비교: 두 문자열의 각 문자가 몇 번 나타나는지를 세어 비교합니다. 만약 두 문자열이 애너그램이라면, 모든 문자의 개수가 동일해야 합니다.
정렬 방법: 두 문자열을 정렬한 후, 정렬된 결과가 동일한지 비교합니다. 이 방법은 두 문자열이 같은 문자로 구성되어 있는지를 쉽게 확인할 수 있습니다.
시간 복잡도 고려: 각 방법에 따라 시간 복잡도가 다르게 나타날 수 있습니다. 문자 개수를 세는 방법은 (O(n)), 정렬하는 방법은 (O(n \log n))의 시간 복잡도를 가집니다.

코드 분석

1. 문자 개수 비교 방법

from collections import Counter

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

동작 원리:
- Counter는 Python의 collections 모듈에 포함된 클래스입니다. 문자열의 각 문자를 키로, 해당 문자의 개수를 값으로 갖는 딕셔너리 형태로 변환합니다.
- 두 문자열의 Counter 결과를 비교하여, 두 문자열이 같은 문자로 구성되어 있는지 확인합니다.
시간 복잡도: (O(n)) - 문자열을 한 번씩 스캔하여 문자 개수를 세므로 선형 시간 복잡도를 가집니다.
공간 복잡도: (O(k)) - 각 문자열에 등장하는 고유 문자 수 k에 따라 공간이 필요합니다.

2. 정렬 방법

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

동작 원리:
- sorted() 함수를 사용하여 두 문자열을 정렬합니다.
- 정렬된 결과를 비교하여, 두 문자열이 애너그램인지 확인합니다.
시간 복잡도: (O(n \log n)) - 정렬은 평균적으로 (O(n \log n))의 시간 복잡도를 가지므로, 이 방법은 문자 개수 비교보다 느립니다.
공간 복잡도: (O(n)) - 정렬된 결과를 저장하기 위한 추가 메모리 공간이 필요합니다.

요약

두 문자열이 애너그램인지 확인하는 문제로, 문자 개수 비교 방법과 정렬 방법 두 가지 접근 방식을 사용할 수 있습니다.
문자 개수 비교는 효율적이고 직관적인 방법으로 (O(n))의 시간 복잡도를 가지며, 공간 복잡도는 (O(k))입니다.
정렬 방법은 더 간단할 수 있지만 시간 복잡도는 (O(n \log n))로 상대적으로 비효율적입니다.