LeetCode

LeetCode 242 Valid Anagram 풀이: 문자 빈도 배열 비교

작성·코드 검증: solve together · 작성 언어: Python

0. 문제 링크와 출처

두 문자열의 문자 구성을 비교하는 문제다. 소문자 영어로 입력이 제한되어 있어 26칸 빈도 배열만으로 해결할 수 있고, 별도의 복잡한 예외 처리가 필요하지 않으므로 Level 1로 판단했다.

1. 문제 요약

문자열 s와 t가 주어질 때, t가 s의 애너그램인지 판정한다. 애너그램은 문자의 순서만 바뀌고 각 문자의 등장 횟수는 같은 문자열이다.

  • 애너그램이면 True, 아니면 False를 반환한다.
  • 두 문자열의 길이는 각각 1 이상 5 * 10^4 이하다.
  • 두 문자열은 소문자 영어로만 구성된다.
  • 순서가 달라도 문자별 등장 횟수가 같아야 한다.

예를 들어 "anagram"과 "nagaram"은 각 문자의 개수가 같으므로 True다. 반면 "rat"과 "car"는 문자 구성이 다르므로 False다.

2. 문제 해결에 사용되는 알고리즘이나 자료구조 설명

문자 빈도 상태

알파벳 a부터 z까지의 개수를 저장하는 길이 26의 배열 count를 사용한다.

두 문자열을 같은 위치에서 동시에 읽으면서 s의 문자는 해당 칸을 +1, t의 문자는 해당 칸을 -1 한다. 순회가 끝난 뒤 모든 값이 0이면 각 문자의 증가분과 감소분이 정확히 상쇄된 것이므로 두 문자열은 애너그램이다.

문자열 길이가 다르면 문자 개수가 같을 수 없으므로 빈도 계산 전에 False를 반환한다.

빈도 차이가 모두 0이면 애너그램인 이유

애너그램 판정에는 문자의 위치가 아니라 각 문자의 총 등장 횟수만 필요하다. 따라서 두 문자열을 정렬해 비교하거나 모든 문자를 별도로 저장하지 않고, 같은 문자에 대한 차이만 누적할 수 있다.

입력이 소문자 영어로 제한되므로 딕셔너리보다 고정된 26칸 배열이 적합하다. s와 t를 동시에 처리하면 한 문자열의 빈도를 만든 뒤 다른 문자열과 비교하는 단계도 줄일 수 있다.

오답 접근과 반례

문자 종류만 비교하고 등장 횟수를 세지 않으면 애너그램이 아닌 문자열을 잘못 인정할 수 있다.

s = "aacc"
t = "ccac"

두 문자열 모두 a와 c를 포함하지만, s는 a와 c가 각각 2개이고 t는 a가 1개, c가 3개다. 따라서 결과는 False여야 한다. 이 문제에서는 문자 종류가 아니라 모든 문자의 빈도를 비교해야 한다.

문자열을 정렬해 sorted(s) == sorted(t)로 비교하는 방법도 정답이다. 하지만 정렬에 O(n log n) 시간이 필요하므로, 소문자 26종이라는 조건을 이용한 빈도 배열이 더 효율적이다.

시간·공간 복잡도

문자열 길이를 n이라고 하면 두 문자열을 한 번씩 확인하므로 시간 복잡도는 O(n)이다. 빈도 배열의 크기는 알파벳 수인 26으로 고정되어 있으므로 추가 공간 복잡도는 O(1)이다.

3. 문제 해결 코드 (Python)

count[index]는 s에서 해당 문자가 나온 횟수와 t에서 나온 횟수의 차이를 나타낸다. 길이가 같은 경우에만 zip으로 두 문자열을 동시에 순회하고, 마지막에 모든 차이가 0인지 확인한다.

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

        count = [0] * 26

        for left, right in zip(s, t):
            count[ord(left) - ord("a")] += 1
            count[ord(right) - ord("a")] -= 1

        return all(value == 0 for value in count)

문제의 입력이 소문자 영어로 제한되므로 ord(character) - ord("a")는 항상 0부터 25 사이의 유효한 인덱스다. 길이가 다를 때 먼저 반환해야 zip이 짧은 문자열에 맞춰 일부 문자만 비교하는 실수를 피할 수 있다.

복사해 실행할 테스트

아래 assert를 풀이 코드와 같은 Python 파일에 붙여 실행하면 빈도 일치, 불일치, 길이 차이를 확인할 수 있다.

solver = Solution()
assert solver.isAnagram("anagram", "nagaram") is True
assert solver.isAnagram("rat", "car") is False
assert solver.isAnagram("ab", "a") is False

4. 공식 예제와 추가 검증

작성한 isAnagram 함수를 Python으로 실행해 공식 예제와 경계 조건을 확인했다.

공식 예제

입력 기대 출력 확인 결과
s = "anagram", t = "nagaram" True 통과
s = "rat", t = "car" False 통과

추가 검증 1: 한 글자 애너그램

입력: s = "a", t = "a"
기대 출력: True
확인 결과: 통과
검증 목적: 최소 길이 입력에서 같은 문자를 처리하는지 확인

추가 검증 2: 길이가 다른 문자열

입력: s = "ab", t = "a"
기대 출력: False
확인 결과: 통과
검증 목적: 빈도 계산 전에 길이 차이를 판정하는지 확인

추가 검증 3: 문자 빈도 불일치

입력: s = "aacc", t = "ccac"
기대 출력: False
확인 결과: 통과
검증 목적: 문자 종류가 아니라 등장 횟수까지 비교하는지 확인

추가 검증 4: 모든 알파벳의 역순

입력: s = "abcdefghijklmnopqrstuvwxyz", t = "zyxwvutsrqponmlkjihgfedcba"
기대 출력: True
확인 결과: 통과
검증 목적: 문자 순서가 달라도 빈도가 같으면 애너그램으로 판정하는지 확인

5. 다른 풀이 방식 검색 및 비교

정렬 방식은 두 문자열을 각각 정렬한 결과를 비교하므로 구현이 짧고 일반적인 문자 집합에도 적용하기 쉽다. 대신 문자열 길이를 n이라 할 때 O(n log n) 시간이 필요하다.

이 글의 빈도 배열 방식은 입력이 소문자 영어라는 조건을 직접 사용해 O(n) 시간에 처리한다. 문자 종류가 고정되지 않은 입력이라면 딕셔너리로 빈도를 세는 방식으로 확장할 수 있지만, 이 문제에서는 26칸 배열이 더 단순하다.

마무리

Valid Anagram은 두 문자열의 순서가 아니라 문자별 등장 횟수를 비교하는 문제다. 한 배열에서 첫 번째 문자열은 더하고 두 번째 문자열은 빼면, 모든 값이 0인지 확인하는 것만으로 애너그램 여부를 판정할 수 있다. 소문자 영어 조건을 활용해 O(n) 시간과 O(1) 추가 공간으로 해결하는 것이 핵심이다.

#해시#LeetCode#난이도 1