문자열 문제를 풀다 보면
단순히 같은 문자인지 비교하는 수준을 넘어서,
특정 문자열로 시작하는 후보를 빠르게 찾는 문제를 만나게 됩니다.
이번 글에서는
검색창이나 명령어 입력창에서 떠올릴 수 있는
자동 추천 기능의 기본형 문제를 정리해보겠습니다.
이 문제는 처음에는 단순 반복문으로도 풀 수 있지만,
검색 요청이 많아질수록 더 효율적인 자료구조가 필요해집니다.
이번 글은 추천 후보를 전부 반환하는 기본형에 가깝고, 상위 몇 개만 잘라서 즉시 추천하는 응용형과는 조금 다릅니다. 즉, 먼저 prefix에 맞는 전체 후보를 모으는 Trie 흐름을 이해하는 데 초점을 둡니다.
문제
음악 앱에서 곡 제목 추천 기능을 만들려고 합니다.
사용자가 검색창에 문자열 keyword를 입력하면,
미리 저장된 곡 제목 목록 중에서
keyword로 시작하는 모든 제목을 반환해야 합니다.
곡 제목 목록과 검색어가 주어질 때,
자동 추천 결과를 반환하는 함수를 작성해보겠습니다.
함수 형식
suggest_titles(keyword, titles)
keyword: 사용자가 입력한 검색어titles: 미리 저장된 곡 제목 목록- 반환값:
keyword로 시작하는 모든 제목 목록
실행 예시
예시 1
입력:
keyword = "mo"
titles = ["moon", "morning", "star", "more"]
출력:
["moon", "morning", "more"]
설명:
"moon"은"mo"로 시작합니다"morning"도"mo"로 시작합니다"more"도"mo"로 시작합니다"star"는 해당하지 않습니다
예시 2
입력:
keyword = "pla"
titles = ["play", "planet", "apple", "plate"]
출력:
["play", "planet", "plate"]
예시 3
입력:
keyword = "xy"
titles = ["dog", "dear", "deal"]
출력:
[]
설명:
"xy"로 시작하는 제목이 없으므로 빈 배열을 반환합니다
처음 떠오르는 생각
가장 먼저 생각할 수 있는 건
목록을 처음부터 끝까지 보면서,
각 문자열이 keyword로 시작하는지 하나씩 확인하는 방식입니다.
예를 들면 이렇게 볼 수 있습니다.
"moon"은"mo"로 시작하는가"morning"은"mo"로 시작하는가"star"는"mo"로 시작하는가
이 방식은 구현은 쉽습니다.
하지만 제목 수가 많고 검색 요청이 자주 들어오면
매번 전체 목록을 훑는 것이 비효율적일 수 있습니다.
핵심 아이디어
이 문제의 핵심은 단순합니다.
입력한 문자열을 접두사(prefix)로 가지는 모든 문자열을 찾기
여기서 prefix는
문자열의 앞부분부터 일치하는 문자열을 말합니다.
예를 들어:
"mo"는"moon"의 접두사입니다"pla"는"planet"의 접두사입니다"de"는"deal"의 접두사입니다
즉,
“문자열이 특정 글자로 시작하는가?”를 빠르게 처리하는 것이 핵심입니다.
먼저 쉬운 풀이부터
가장 단순한 방법은 리스트를 순회하면서
startswith()로 검사하는 것입니다.
def suggest_titles(keyword, titles):
result = []
for title in titles:
if title.startswith(keyword):
result.append(title)
return result
이 방법은 이해하기 쉽고 구현도 간단합니다.
예시
titles = ["moon", "morning", "star", "more"]
print(suggest_titles("mo", titles))
출력:
['moon', 'morning', 'more']
이 풀이의 한계
이 방식은 검색 한 번마다
제목 목록 전체를 다시 확인해야 합니다.
즉, 데이터가 많고 검색 요청이 자주 들어오면
계속 같은 비교를 반복하게 됩니다.
예를 들어 제목이 10만 개 있는데
사용자가 "m", "mo", "mor"처럼 계속 입력하면
매번 처음부터 다시 확인하게 됩니다.
그래서 문제 힌트처럼
미리 더 효율적인 형태로 전처리해두는 방법을 생각할 수 있습니다.
더 효율적인 자료구조: Trie
이 문제에서 자주 나오는 자료구조가 **Trie(트라이)**입니다.
Trie는 문자열을 글자 단위로 나눠서 저장하는 트리 구조입니다.
예를 들어 "moon", "more"를 저장하면
앞의 "mo" 부분을 공유할 수 있습니다.
간단히 그림처럼 생각하면:
(root)
└─ m
└─ o
├─ o
│ └─ n
└─ r
└─ e
즉, 같은 접두사를 가지는 문자열들이
앞부분 노드를 함께 사용합니다.
이 구조를 쓰면:
"mo"까지 빠르게 이동하고- 그 아래에 있는 모든 단어를 모아서 반환
하는 방식으로 처리할 수 있습니다.
이 점이 이번 글의 핵심입니다. 이번 문제는 특정 prefix 아래에 달린 모든 후보를 DFS처럼 수집하는 기본형 Trie를 다룹니다. 즉, 노드마다 추천 결과를 미리 저장하는 응용형보다 조금 더 교과서적인 Trie 흐름에 가깝습니다.
왜 Trie가 잘 맞을까
이 문제는 “정확히 같은 단어 찾기”보다
같은 시작 부분을 가진 단어 모으기가 중요합니다.
Trie는 바로 그 상황에 잘 맞습니다.
- 공통 접두사를 공유할 수 있습니다
- 특정 prefix 위치까지 빠르게 내려갈 수 있습니다
- 그 아래에 있는 후보를 쉽게 수집할 수 있습니다
즉, 검색 횟수가 많아질수록 장점이 커집니다.
코드
Trie 노드 구조
파이썬에서는 보통 이런 식으로 노드를 만들 수 있습니다.
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
각 노드는:
children: 다음 문자로 가는 길is_end: 여기서 단어가 끝나는지 여부
를 가집니다.
Trie에 단어 넣기
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for ch in word:
if ch not in node.children:
node.children[ch] = TrieNode()
node = node.children[ch]
node.is_end = True
이렇게 하면 단어를 한 글자씩 따라가며 저장할 수 있습니다.
prefix로 시작하는 후보 찾기
이제 검색어 위치까지 내려간 뒤,
그 아래 단어들을 모두 모으면 됩니다.
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for ch in word:
if ch not in node.children:
node.children[ch] = TrieNode()
node = node.children[ch]
node.is_end = True
def _collect_words(self, node, path, result):
if node.is_end:
result.append(path)
for ch, next_node in node.children.items():
self._collect_words(next_node, path + ch, result)
def autocomplete(self, prefix):
node = self.root
for ch in prefix:
if ch not in node.children:
return []
node = node.children[ch]
result = []
self._collect_words(node, prefix, result)
return result
코드 해설
1. 단어들을 Trie에 미리 저장
모든 문자열을 Trie에 넣어 둡니다.
for word in words:
trie.insert(word)
이 과정이 전처리입니다.
2. prefix까지 따라 내려가기
예를 들어 "mo"를 찾는다면
- root에서
m으로 이동 m에서o로 이동
이렇게 prefix 위치까지 내려갑니다.
3. 그 아래 단어 전부 수집
"mo" 아래에 연결된 모든 경로를 따라가면
"moon", "morning", "more" 같은 단어를 찾을 수 있습니다.
즉, prefix 위치를 시작점으로 해서
하위 단어를 모두 모으는 방식입니다.
사용 예시
words = ["moon", "morning", "star", "more"]
trie = Trie()
for word in words:
trie.insert(word)
print(trie.autocomplete("mo"))
출력 예시:
['moon', 'morning', 'more']
복잡도
단순 리스트 순회
검색할 때마다 전체 목록을 확인해야 하므로
데이터가 많아질수록 느려질 수 있습니다.
Trie 사용
- 전처리에 시간이 들지만
- 검색어 prefix 위치까지는 빠르게 이동할 수 있고
- 그 아래 후보만 모으면 됩니다
즉,
검색이 자주 일어나는 상황에서는 Trie가 더 유리합니다.
정리
이 문제의 핵심은 한 줄입니다.
입력한 문자열을 접두사로 가지는 모든 문자열을 빠르게 찾는 것
기본 풀이는 리스트를 순회하면서 확인하면 되고,
검색 요청이 많다면 Trie로 전처리해서 더 효율적으로 만들 수 있습니다.
특히 이 글은 prefix에 맞는 전체 후보를 반환하는 기본형을 다룹니다. 나중에 추천 후보를 상위 3개만 유지하거나, 노드에 미리 추천 결과를 저장하는 응용형으로 확장할 때도 이 기본형 흐름을 알고 있으면 훨씬 이해하기 쉽습니다.
즉, 이 문제는
- 문자열 비교
- prefix 개념
- 전처리
- Trie 자료구조
이 네 가지를 함께 연습하기 좋은 문제입니다.
※ 이 글의 문제 상황과 예시는 학습용으로 직접 재구성한 내용입니다.