View in English →

Code › algorithm-study

LeetCode 242 - Valid Anagram

Valid Anagram 문제를 정렬과 character count 관점에서 비교한 풀이

algorithmleetcodestringhash-mapsortingpythonlearning

이번 문제는 두 문자열이 같은 문자 요소로 만들어졌는지 확인하는 문제다. 난이도는 Easy이고, 정렬해서 비교하는 방법과 character count를 저장해서 비교하는 방법을 나눠 보았다.

문제 링크 & 설명

  • 문제 링크: 242. Valid Anagram
  • 요약: 문자열 s와 t가 주어졌을 때, 두 문자열이 anagram이면 true, 아니면 false를 반환하는 문제다.

anagram은 사용하는 문자의 종류와 개수가 같은 문자열이다. 순서는 달라도 되지만, 각 문자가 등장한 횟수는 같아야 한다.

예를 들어 이렇게 주어졌다고 해보자.

s = "anagram"
t = "nagaram"

두 문자열은 문자 순서가 다르지만, 각각의 문자를 세어보면 구성은 같다. 그래서 결과는 true다.

반대로 이런 경우는 다르다.

s = "rat"
t = "car"

길이는 같지만 문자 구성이 다르므로 결과는 false다.

이 문제를 처음 보면 문자열을 정렬해서 비교하는 방식이 가장 바로 떠오른다. anagram은 순서가 다른 같은 문자 묶음이기 때문에, 두 문자열을 같은 기준으로 정렬했을 때 결과가 같으면 같은 구성이라고 판단할 수 있다. 다만 정렬은 비용이 들어가고, 문자 개수만 비교하면 정렬 없이도 같은 결론을 낼 수 있다.

접근 방법

1. 정렬해서 비교하기

가장 단순한 풀이는 두 문자열을 정렬한 뒤 결과가 같은지 비교하는 것이다. 순서만 다르고 문자 구성이 같다면 정렬 결과는 동일해진다.

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

이 방식은 코드가 짧고 명확하다. 문자열의 길이를 따로 확인하지 않아도, 길이가 다르면 정렬 결과도 달라지므로 false이다.

대신 정렬 비용이 있다. 길이가 n인 문자열을 정렬하면 시간복잡도는 O(n log n)이고, Python의 sorted 함수는 정렬된 리스트를 새로 만들기 때문에 추가 공간도 필요하다.

2. character count 저장하기

정렬하지 않고 풀려면 각 문자가 몇 번 등장했는지 세면 된다. 먼저 문자열 s를 순회하면서 문자별 개수를 dictionary에 저장하고, 그 다음 문자열 t를 순회하면서 같은 문자의 개수를 하나씩 줄인다.

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

        char_map: Dict[str, int] = {}
        for ch in s:
            char_map[ch] = char_map.get(ch, 0) + 1

        for ch in t:
            if ch not in char_map or char_map[ch] == 0:
                return False

            char_map[ch] -= 1

        return True

길이가 다르면 anagram이 될 수 없으므로 먼저 반환한다. 길이가 같다면 s에서 만든 문자 개수표를 기준으로 t의 문자를 하나씩 상쇄한다.

여기서 중요한 조건은 현재 문자가 개수표에 없거나, 이미 남은 개수가 0인지 확인하는 부분이다. t에 s에 없던 문자가 나오거나, 이미 필요한 개수보다 더 많이 나온 문자가 있으면 anagram이 아니다. 이 조건을 통과한 문자만 개수를 하나 줄인다.

복잡도 분석

1. 정렬 방식

  • 시간 복잡도: O(n log n)

    • 두 문자열을 정렬해야 하므로 정렬 비용이 중심이 된다. 여기서 n은 문자열 길이다.

  • 공간 복잡도: O(n)

    • Python의 sorted 함수는 정렬된 리스트를 새로 만든다.

2. character count 방식

  • 시간 복잡도: O(n + m)

    • 문자열 s와 t를 각각 한 번씩 순회한다. 길이가 같다는 조건을 먼저 확인하므로 보통은 O(n)으로 정리할 수 있다.

  • 공간 복잡도: O(k)

    • dictionary에는 등장한 문자 종류만 저장된다. k는 고유 문자 수이고, 최악의 경우 입력 크기에 비례할 수 있다. 문제 조건처럼 소문자 영어만 들어온다면 길이 26짜리 배열로도 같은 count를 저장할 수 있고, 이 경우 공간복잡도는 문자 집합 크기에 고정된다.

구현 코드

최종 코드는 character count 방식으로 정리했다. 정렬보다 코드가 조금 길지만, 문자열을 정렬하지 않고 한 번씩 순회하면서 문자 개수를 비교할 수 있다.

from typing import Dict

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

        char_map: Dict[str, int] = {}

        for ch in s:
            char_map[ch] = char_map.get(ch, 0) + 1

        for ch in t:
            if ch not in char_map or char_map[ch] == 0:
                return False

            char_map[ch] -= 1

        return True

요약 및 회고

이 문제는 anagram을 순서 문제가 아니라 문자 개수 문제로 바꿔서 보는 것이 핵심이었다. 정렬 방식은 두 문자열의 순서를 같은 기준으로 맞춘 뒤 비교하는 방법이고, character count 방식은 각 문자의 등장 횟수를 직접 비교하는 방법이다.

정렬 풀이는 간단하고 실수할 여지가 적지만 시간복잡도는 O(n log n)이다. dictionary를 쓰면 각 문자의 개수를 저장하고 상쇄하면서 O(n)에 확인할 수 있다. 입력이 소문자 영어로 제한되어 있다면 dictionary 대신 길이 26 배열을 쓰는 방식도 가능하고, 이 경우 hash map보다 더 작은 고정 크기 메모리로 처리할 수 있다. 결국 이 문제에서는 문자열의 순서를 맞추는 대신, 문자별 개수라는 상태를 만들어두면 더 직접적으로 anagram 여부를 판단할 수 있다.