[Collections] defaultdict 알아보기 - 코딩 테스트에서의 defaultdict 활용하기

Python의 defaultdict는 기본값을 자동으로 생성하는 딕셔너리로, 단순한 문제 해결뿐만 아니라 코딩 테스트에서도 매우 유용하게 사용된다. 이번 글에서는 defaultdict의 심화된 활용 방법과 코딩 테스트에서 어떤 상황에서 활용하면 좋은지 중점적으로 다룬다.

---

1. 기본 개념 복습

defaultdict는 Python의 collections 모듈에서 제공하며, 기본값 생성 함수를 설정하여 키가 존재하지 않을 때 자동으로 기본값을 생성한다. 이는 KeyError를 방지하고 코드의 가독성을 높이는 데 도움을 준다.

기본 사용법

from collections import defaultdict

d = defaultdict(int)
d['a'] += 1  # 키 'a'가 없으면 0으로 초기화한 후 1을 더함
print(d['a'])  # 출력: 1
print(d['b'])  # 출력: 0 (자동 초기화)

---

2. 코딩 테스트에서 defaultdict가 유용한 이유

코딩 테스트에서는 제한된 시간 내에 문제를 해결해야 하므로, 코드의 효율성과 간결성이 중요하다. defaultdict는 다음과 같은 상황에서 특히 유용하다:

1. 초기화가 필요한 자료구조: 데이터를 그룹화하거나 누적해야 할 때.
2. KeyError 방지: 미리 키를 체크하지 않고 값을 바로 업데이트할 수 있음.
3. 코드 가독성 향상: 초기화 코드 없이 데이터 처리 논리에 집중 가능.

---

3. 주요 활용 사례

3.1 데이터 그룹화

특정 기준으로 데이터를 그룹화해야 하는 경우 defaultdict를 활용하면 간단히 해결할 수 있다.

문제 예시: 각 단어의 첫 글자를 기준으로 단어를 그룹화하라.

from collections import defaultdict

words = ["apple", "banana", "cherry", "apricot", "blueberry"]
grouped = defaultdict(list)

for word in words:
    grouped[word[0]].append(word)

print(dict(grouped))  # 출력: {'a': ['apple', 'apricot'], 'b': ['banana', 'blueberry'], 'c': ['cherry']}

코딩 테스트 응용

• 유형: 문자열 처리 문제
• 활용: 문자열의 특정 패턴에 따라 그룹화하여 후속 작업을 수행.

---

3.2 카운팅 작업

값의 빈도를 계산할 때 defaultdict(int)를 사용하면 효율적이다.

문제 예시: 주어진 숫자 리스트에서 각 숫자의 빈도를 계산하라.

from collections import defaultdict

nums = [1, 2, 2, 3, 3, 3, 4]
counter = defaultdict(int)

for num in nums:
    counter[num] += 1

print(dict(counter))  # 출력: {1: 1, 2: 2, 3: 3, 4: 1}

코딩 테스트 응용

• 유형: 배열 또는 문자열 빈도 계산 문제
• 활용: 특정 조건에 따라 최빈값을 찾거나 빈도를 기반으로 문제를 해결.

---

3.3 그래프 생성

그래프 문제에서 인접 리스트를 생성할 때 defaultdict(list)를 사용하면 코드가 간결해진다.

문제 예시: 주어진 간선 리스트를 기반으로 그래프를 생성하라.

from collections import defaultdict

edges = [(1, 2), (1, 3), (2, 4), (3, 4)]
graph = defaultdict(list)

for u, v in edges:
    graph[u].append(v)
    graph[v].append(u)  # 무방향 그래프인 경우

print(dict(graph))  # 출력: {1: [2, 3], 2: [1, 4], 3: [1, 4], 4: [2, 3]}

코딩 테스트 응용

• 유형: 그래프 탐색 (BFS, DFS) 문제
• 활용: 인접 리스트 생성 및 탐색에 유용.

---

3.4 조건부 데이터 처리

조건에 따라 데이터를 누적하거나 분리해야 할 때 유용하다.

문제 예시: 학생들의 점수를 과목별로 누적하라.

from collections import defaultdict

data = [
    ("Alice", "Math", 90),
    ("Bob", "Math", 85),
    ("Alice", "Science", 95),
    ("Bob", "Science", 80)
]

scores = defaultdict(list)

for student, subject, score in data:
    scores[subject].append((student, score))

print(dict(scores))
# 출력: {'Math': [('Alice', 90), ('Bob', 85)], 'Science': [('Alice', 95), ('Bob', 80)]}

코딩 테스트 응용

• 유형: 데이터 분류 및 정렬 문제
• 활용: 조건에 따라 데이터를 정리한 후 특정 연산 수행.

---

3.5 다중 딕셔너리 초기화

딕셔너리 안에 딕셔너리가 중첩된 자료구조를 초기화해야 할 때 defaultdict를 사용하면 코드가 단순해진다.

문제 예시: 2차원 좌표에 값을 누적하라.

from collections import defaultdict

data = [
    ("x", 1, 10),
    ("x", 2, 20),
    ("y", 1, 30),
    ("y", 2, 40)
]

matrix = defaultdict(lambda: defaultdict(int))

for axis, index, value in data:
    matrix[axis][index] += value

print(dict(matrix))
# 출력: {'x': {1: 10, 2: 20}, 'y': {1: 30, 2: 40}}

코딩 테스트 응용

• 유형: 다차원 배열 문제
• 활용: 딕셔너리를 기반으로 한 동적 프로그래밍(DP) 문제.

---

4. defaultdict의 시간 복잡도

defaultdict의 기본 연산은 일반적인 딕셔너리와 동일하게 O(1)이다. 다만, 새로운 키를 생성할 때 기본값 생성 함수가 호출되므로 이 함수의 시간 복잡도에 따라 추가 비용이 발생할 수 있다. 따라서 기본값 생성 함수가 복잡한 연산을 포함하지 않도록 주의해야 한다.

---

5. 결론

Python의 defaultdict는 코딩 테스트에서 초기화와 데이터 처리의 복잡성을 줄이고, 가독성과 효율성을 높이는 데 매우 유용하다. 데이터를 그룹화하거나 빈도를 계산하고, 그래프를 생성하는 문제와 같은 다양한 상황에서 활용할 수 있다. defaultdict를 적극적으로 활용하여 코딩 테스트에서 시간을 절약하고 더 나은 코드를 작성해 보자!