문자열 문제를 풀다 보면
단순히 같은 문자열을 찾는 것을 넘어서,
입력 중인 문자열을 기준으로 후보를 추천하는 문제를 만나게 됩니다.

이번 글에서는
터미널이나 명령어 팔레트에서 떠올릴 수 있는
명령어 자동 추천 기능의 응용형 문제를 정리해보겠습니다.

이 문제는 처음에는 리스트를 순회하면서도 풀 수 있지만,
검색 요청이 많아질수록 접두사 검색에 맞는 자료구조가 더 잘 맞습니다.

특히 이번 글은 prefix에 맞는 후보를 전부 반환하는 기본형보다 한 단계 더 나아가, 사전순 상위 3개만 즉시 반환하도록 Trie 노드를 설계하는 방식에 초점을 둡니다.

문제

개발 도구에서 명령어 추천 기능을 만들려고 합니다.

사용자가 문자열 prefix를 입력하면,
미리 등록된 명령어 목록 중에서
prefix로 시작하는 명령어를 사전순으로 최대 3개까지 추천해야 합니다.

명령어 목록과 검색어가 주어질 때,
추천 결과를 반환하는 함수를 작성해보겠습니다.

함수 형식

suggest_commands(prefix, commands)
  • prefix: 사용자가 입력한 문자열
  • commands: 미리 저장된 명령어 목록
  • 반환값: prefix로 시작하는 추천 명령어 최대 3개

실행 예시

예시 1

입력:
prefix = "gi"
commands = ["git", "gimp", "gist", "grep"]

출력:
["gimp", "gist", "git"]

설명:

  • "gimp", "gist", "git"은 모두 "gi"로 시작합니다
  • "grep"는 "gi"로 시작하지 않으므로 제외합니다
  • 결과는 사전순으로 정렬한 뒤 최대 3개까지만 반환합니다

예시 2

입력:
prefix = "do"
commands = ["docker", "docs", "domain", "dotnet", "git"]

출력:
["docker", "docs", "domain"]

설명:

  • "docker", "docs", "domain", "dotnet"이 후보입니다
  • 이 중 사전순으로 앞선 3개만 남기면 됩니다

예시 3

입력:
prefix = "zz"
commands = ["git", "grep", "docker"]

출력:
[]

설명:

  • "zz"로 시작하는 명령어가 없으므로 빈 배열을 반환합니다

처음 떠오르는 생각

가장 먼저 생각할 수 있는 방법은
명령어 목록을 처음부터 끝까지 보면서
각 문자열이 prefix로 시작하는지 하나씩 확인하는 방식입니다.

예를 들면 이렇게 볼 수 있습니다.

  • "git"은 "gi"로 시작하는가
  • "gimp"는 "gi"로 시작하는가
  • "grep"는 "gi"로 시작하는가

이 방식은 이해하기 쉽고 구현도 간단합니다.
다만 검색어가 자주 들어오고 명령어 수가 많아질수록
매번 전체 목록을 다시 확인하는 것이 아쉬워집니다.

핵심 아이디어

이 문제의 핵심은 두 가지입니다.

  1. 접두사(prefix)로 시작하는 문자열을 찾는다
  2. 그중 사전순으로 앞선 최대 3개만 반환한다

즉, 단순히 접두사 일치 여부만 보는 것이 아니라
추천 후보를 작은 개수로 잘라서 바로 꺼내올 수 있게 만드는 것이 중요합니다.

이 관점에서 보면 Trie를 조금 변형해서 쓰는 방법이 잘 맞습니다.

기본형 Trie가 prefix 아래 후보를 나중에 전부 모으는 구조라면, 이번 문제는 각 prefix 노드가 이미 상위 3개 추천 결과를 들고 있는 구조에 가깝습니다. 그래서 검색 시점의 비용을 더 줄이는 응용 문제로 볼 수 있습니다.

먼저 쉬운 풀이부터

가장 단순한 방법은 리스트를 순회하면서
startswith()로 검사한 뒤, 정렬하고 앞에서 3개를 자르는 것입니다.

def suggest_commands(prefix, commands):
    matches = []

    for command in commands:
        if command.startswith(prefix):
            matches.append(command)

    matches.sort()
    return matches[:3]

이 방식은 한 번의 검색에는 충분히 괜찮습니다.

예시

commands = ["git", "gimp", "gist", "grep"]
print(suggest_commands("gi", commands))

출력:

['gimp', 'gist', 'git']

이 풀이의 한계

이 방식은 검색할 때마다

  • 전체 목록을 다시 순회하고
  • 후보를 다시 정렬해야 합니다

예를 들어 사용자가 "g", "gi", "git"처럼
한 글자씩 입력할 때마다
비슷한 작업을 계속 반복하게 됩니다.

즉, 검색이 자주 일어나는 상황에서는
미리 검색하기 좋은 구조로 저장해두는 편이 더 낫습니다.

더 효율적인 자료구조: Trie

이 문제에서 잘 맞는 자료구조가 **Trie(트라이)**입니다.

Trie는 문자열을 글자 단위로 나눠 저장하는 트리 구조입니다.

예를 들어 "git", "gimp", "gist"를 저장하면
앞부분 "gi"를 공유할 수 있습니다.

간단히 생각하면 이런 느낌입니다.

(root)
 └─ g
     └─ i
         ├─ t
         ├─ m
         │   └─ p
         └─ s
             └─ t

여기서 한 단계 더 나가서,
각 노드마다 그 prefix에서 추천할 수 있는 상위 3개 후보를 미리 저장해 둘 수 있습니다.

그러면 검색할 때는:

  • prefix 위치까지 내려가고
  • 그 노드에 저장된 추천 목록을 바로 반환

하면 됩니다.

왜 이 방식이 잘 맞을까

이 문제는 모든 후보를 다 모은 뒤 정렬하는 것보다
각 prefix에서 자주 쓰일 추천 결과를 미리 유지하는 편이 더 효율적입니다.

즉, 이 글의 Trie는
“prefix 아래 모든 문자열을 나중에 수집하는 구조”보다
각 prefix 노드가 이미 추천 결과 일부를 들고 있는 구조에 가깝습니다.

이렇게 하면 검색 시점에는

  • prefix까지 내려가기
  • 저장된 최대 3개를 그대로 반환하기

정도만 하면 됩니다.

코드

class TrieNode:
    def __init__(self):
        self.children = {}
        self.top3 = []


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.top3.append(word)
            node.top3.sort()

            if len(node.top3) > 3:
                node.top3.pop()

    def suggest(self, prefix):
        node = self.root

        for ch in prefix:
            if ch not in node.children:
                return []
            node = node.children[ch]

        return node.top3


def suggest_commands(prefix, commands):
    trie = Trie()

    for command in commands:
        trie.insert(command)

    return trie.suggest(prefix)

코드 해설

1. 각 노드에 추천 목록 저장하기

self.top3 = []

이번 구현에서는 노드마다
그 prefix에서 추천할 수 있는 최대 3개 후보를 저장합니다.

즉, "gi" 노드에 도착했을 때
이미 ["gimp", "gist", "git"] 같은 결과가 들어 있도록 만드는 방식입니다.

2. 단어를 넣을 때 prefix별 추천 목록 갱신하기

node.top3.append(word)
node.top3.sort()

if len(node.top3) > 3:
    node.top3.pop()

단어를 삽입하면서 지나가는 모든 prefix 노드에
현재 단어를 후보로 넣습니다.

그다음:

  • 사전순 정렬
  • 3개 초과 시 뒤에서 제거

를 하면, 각 노드는 항상 “사전순 상위 3개”만 유지하게 됩니다.

3. 검색은 prefix 위치까지만 이동

for ch in prefix:
    if ch not in node.children:
        return []
    node = node.children[ch]

검색할 때는 prefix 위치까지 내려갑니다.

여기서 경로가 끊기면
해당 prefix로 시작하는 명령어가 없다는 뜻이므로 빈 배열을 반환합니다.

4. 그 노드의 추천 목록 바로 반환

return node.top3

이 방식의 핵심입니다.

기존처럼 하위 전체를 다시 모으는 것이 아니라,
노드에 저장된 추천 목록을 그대로 꺼내면 끝입니다.

실행 예시

commands = ["git", "gimp", "gist", "grep"]
print(suggest_commands("gi", commands))

출력:

['gimp', 'gist', 'git']

복잡도

단순 리스트 순회

  • 검색할 때마다 전체 목록을 확인해야 합니다
  • 후보가 많으면 정렬 비용도 다시 들어갑니다

Trie 사용

  • 전처리 시 문자열을 넣는 비용이 듭니다
  • 대신 검색 시에는 prefix 길이만큼만 내려가면 됩니다
  • 각 노드에 최대 3개만 유지하므로 추천 목록 처리는 작게 끝납니다

즉, 검색 요청이 자주 들어오는 상황에서 더 잘 맞습니다.

정리

이 문제의 핵심은 한 줄입니다.

입력한 접두사에 대해, 사전순 상위 3개 후보를 빠르게 꺼내오는 것

기본 풀이는 리스트를 순회하면서 구현할 수 있고,
검색 요청이 많다면 Trie를 이용해 더 효율적으로 만들 수 있습니다.

특히 이번 문제는
단순히 모든 후보를 찾는 것보다
prefix별 추천 결과를 미리 저장해둘 수 있다는 점이 포인트입니다.

즉, 이 글은 자동 추천 기본형보다 한 단계 더 나아간 버전입니다. 후보 전체를 수집하는 Trie 흐름을 알고 있다면, 이번 응용형은 “무엇을 미리 저장해둘 것인가”의 차이로 이해할 수 있습니다.

즉, 이 문제는

  • 접두사 검색
  • 문자열 자료구조
  • 전처리
  • Trie 응용

을 함께 연습하기 좋은 유형입니다.

※ 이 글의 문제 상황과 예시는 학습용으로 직접 재구성한 내용입니다.