View in English →

Code › algorithm-study

LeetCode 49 - Group Anagrams

정렬한 문자열을 key로 삼아 anagram 문자열들을 묶는 Python 풀이

algorithmleetcodearraystringhash-mapsortingpythonlearning

문자열 배열에서 anagram끼리 묶어 반환하는 Medium 문제다. 이번 풀이는 각 문자열을 정렬한 값을 hash map의 key로 쓰고, 원래 문자열은 그 key에 해당하는 list에 모으는 방식으로 정리했다.

문제 링크 & 설명

  • 문제 링크: 49. Group Anagrams
  • 요약: 문자열 배열 strs가 주어졌을 때, 서로 anagram인 문자열들을 같은 그룹으로 묶어 반환하는 문제.

anagram은 같은 문자를 같은 개수만큼 사용하지만 순서만 다른 문자열이다. 예를 들어 eat, tea, ate는 모두 e, a, t를 한 번씩 사용하므로 같은 그룹에 들어간다.

입력이 이렇게 주어진다고 해보자.

strs = ["eat", "tea", "tan", "ate", "nat", "bat"]

가능한 결과는 다음과 같다.

[["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]

문제에서 그룹의 순서나 그룹 안 문자열의 순서는 중요하지 않고, 핵심은 어떤 문자열들이 같은 문자 구성으로 만들어졌는지 판별하는 기준을 잡는 데 있다.

접근 방법

anagram을 비교할 때 문자열의 원래 순서는 방해가 되는데, eat와 tea는 다르게 생겼어도 같은 기준으로 정렬하면 둘 다 aet가 된다. 그래서 각 문자열을 정렬한 결과를 대표 key로 쓸 수 있다.

sorted_str = "".join(sorted(str))

Python의 sorted 함수는 문자열을 문자 단위로 정렬한 list를 반환한다. 이 list를 다시 문자열로 합치면 hash map의 key로 사용할 수 있고, 같은 anagram 그룹은 항상 같은 key를 공유한다.

그 다음에는 defaultdict를 사용해서 key별 list를 만든다. 아직 없는 key에 접근해도 빈 list가 자동으로 만들어지기 때문에, 매번 key 존재 여부를 확인하지 않고 원래 문자열을 바로 append할 수 있다.

groups = defaultdict(list)

for str in strs:
    sorted_str = "".join(sorted(str))
    groups[sorted_str].append(str)

예를 들어 eat를 정렬하면 aet가 되고, tea와 ate도 같은 key인 aet로 들어간다. tan과 nat는 ant key로 묶이고, bat는 abt key에 혼자 남는다.

마지막에는 dictionary의 values만 꺼내 2차원 list 형태로 반환한다.

return list(groups.values())

이 풀이의 핵심은 문자열 하나하나를 직접 서로 비교하지 않는다는 점이다. 모든 쌍을 비교하면 입력이 커질수록 비교 횟수가 빠르게 늘어나지만, 정렬된 문자열 key를 만들어두면 각 단어는 자기 key에 해당하는 그룹으로 한 번만 들어가면 된다.

복잡도 분석

문자열 개수를 N, 문자열 하나의 최대 길이를 L이라고 두면 다음과 같이 정리할 수 있다.

  • 시간 복잡도: O(N × L log L)

    • 각 문자열을 한 번씩 순회하고, 문자열마다 길이 L 기준으로 정렬한다. 문자열별 실제 길이를 모두 더해 쓰면 Σ Li log Li이고, 최대 길이 L로 묶어 표현하면 O(N × L log L)이다.

  • 공간 복잡도: O(N × L)

    • hash map에는 정렬된 문자열 key와 그룹 list가 저장된다. 반환 결과에 원래 문자열들이 모두 포함되고, key 문자열도 입력 크기에 비례해서 쌓일 수 있다.

정렬 과정에서는 각 단어마다 임시 list와 key 문자열도 만들어진다. 한 단어를 처리하는 동안의 임시 공간은 단어 길이에 비례하지만, 전체 결과와 key들을 포함해서 보면 공간은 입력 전체 문자 수에 비례한다.

구현 코드

from collections import defaultdict
from typing import List

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        groups = defaultdict(list)

        for str in strs:
            sorted_str = "".join(sorted(str))
            groups[sorted_str].append(str)

        return list(groups.values())

요약 및 회고

이 문제는 anagram 판별을 매번 두 문자열 비교로 처리하지 않고, 같은 문자 구성이라면 같은 key로 모이게 만드는 문제다. 문자열을 정렬하면 순서 차이가 사라지고, 남는 것은 문자 구성뿐이다.

정렬 key 방식은 시간복잡도가 O(N × L log L)이라서 문자 개수를 세는 방식보다 이론적으로 더 비쌀 수 있다. 대신 구현이 짧고, 각 문자열을 어떤 그룹에 넣어야 하는지 바로 드러난다. 이번 풀이에서는 defaultdict로 그룹 생성 처리를 단순하게 만들고, 정렬된 문자열을 anagram의 대표값으로 사용했다.