← 전체 회차
A-004● Day 042026.05.07mediumleetcode #49neetcode150

애너그램 그룹화

#array#hash-table#string#sorting
↗ leetcode #49 · group-anagrams
01

문제

· problem
P.004

애너그램 그룹화

↗ leetcode #49

문자열 배열 strs가 주어졌을 때, 애너그램끼리 그룹화하여 반환하세요. 답은 어떤 순서로든 반환할 수 있습니다.

제약
  • · 1 ≤ strs.length ≤ 10^4
  • · 0 ≤ strs[i].length ≤ 100
  • · strs[i] consists of lowercase English letters
// 지문은 본인 언어 요약 — 원문은 위 링크에서
입출력 예시
example 1input → output
["eat","tea","tan","ate","nat","bat"]
[["eat","tea","ate"],["tan","nat"],["bat"]]
example 2input → output
[""]
[[""]]
example 3input → output
["a"]
[["a"]]
02

사전 사고

· pre-solve
● 1리스트 출력→● 2선택→● 3정답 공개
  • ☐
    두 문자열이 애너그램이 되는 조건은 무엇인가요?
  • ☐
    문자열의 모든 애너그램을 식별하는 고유한 서명을 어떻게 만들 수 있나요?
  • ☐
    문자열들을 공유 서명으로 효율적으로 그룹화할 수 있는 자료구조는?
  • ☐
    출력에서 그룹들의 순서가 중요한가요?
  • ☐
    입력 배열을 먼저 정렬할 필요가 있나요?
  • ☐
    반환 전 각 그룹의 문자열들을 정렬해야 하나요?
  • ☐
    문자 빈도 대신 정렬된 문자열을 키로 사용할 수 있나요?
던질 질문에 체크하고 확인을 누르세요
// 결과는 세션 메모리만 — 새로고침하면 초기화됩니다 (반복 학습)
03

논리 구조

· logic
● 1슬롯 출력→● 2슬롯별 선택→● 3정답 공개
// 각 슬롯에 들어갈 코드 한 줄을 골라 알고리즘 흐름을 합성해보세요. 코드는 안 짜지만 논리 뼈대는 직접.
step 1· 결과 딕셔너리 초기화
○
groups = {}
○
groups = collections.defaultdict(list)
○
groups = []
step 2· 각 문자열을 순회
○
for s in strs: # O(m)
○
for i in range(len(strs)): s = strs[i]
○
for s in strs[::-1]:
step 3· 문자 빈도 계산│ 중첩
○
count[char] = count.get(char, 0) + 1
○
count[char] += 1
○
count[char] = 1
step 4· 빈도로부터 표준 키 생성│ 중첩
○
tup = tuple(sorted(count.items())) # O(1) because there is limited amount of possible keys in the alphabet -> O(26) + O(26*log26) + O(26)
○
tup = sorted(count.items())
○
tup = tuple(count.keys())
step 5· 문자열을 그룹에 추가│ 중첩
○
groups[tup].append(s)
○
groups[tup] = [s]
○
groups.append((tup, s))
step 6· 그룹화된 결과 반환
○
return list(groups.values())
○
return groups
○
return list(groups.keys())
각 슬롯에 한 줄씩 골라보세요
// format: slot — 다른 패턴(재귀·DP 등) 은 ordering·state-first 등 별도 format. ADR-08 후속.
04

문제풀이 · 트레이스

· solve
solution.py
1
class Solution:
2
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
3
        groups = {}
4
5
        # Iterate over strings
6
        for s in strs: # O(m)
7
            count = {}
8
9
            # Count frequency of each character
10
            for char in s: # O(n)
11
                count[char] = count.get(char, 0) + 1
12
13
            # Convert count Dict to List, sort it, and then convert to Tuple (we cannot use dicts or lists as keys in a hashmap)
14
            tup = tuple(sorted(count.items())) # O(1) because there is limited amount of possible keys in the alphabet -> O(26) + O(26*log26) + O(26)
15
16
            if tup in groups:
17
                groups[tup].append(s)
18
            else:
19
                groups[tup] = [s] 
20
            
21
        return list(groups.values())
22
    
23
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
24
        ans = collections.defaultdict(list)
25
26
        for s in strs:
27
            count = [0] * 26
28
            for c in s:
29
                count[ord(c) - ord("a")] += 1
30
            ans[tuple(count)].append(s)
31
        return list(ans.values())
머릿속 dry-run 케이스
// 각 케이스를 머릿속으로 따라가보세요. 막히면 아래 worked example 펼침.
case 1
["eat","tea","tan","ate","nat","bat"]
→
[["eat","tea","ate"],["tan","nat"],["bat"]]
case 2
[""]
→
[[""]]
case 3
["a"]
→
[["a"]]
// UI 가 walk-through 안 함 — 학습자가 머릿속으로. 막히면 worked example 펼침.