문제 개요
소문자로만 이루어진 문자열들의 리스트 w가 주어졌다고 가정해 보겠습니다. 이때 w에서 만들 수 있는 가장 긴 시퀀스의 길이를 구해야 합니다. 여기서 유효한 시퀀스란, 각 이전 단어가 다음 단어의 접두사(prefix)이면서, 다음 단어는 이전 단어에 새로운 문자를 정확히 하나만 추가한 형태여야 하는 시퀀스를 의미합니다.
예를 들어 입력이 w = ["pqr", "pq", "m", "mn", "pqrs"]라고 해보겠습니다. 이 경우 출력은 3이 됩니다. 왜냐하면 ["pq", "pqr", "pqrs"]라는 시퀀스를 만들 수 있고, 각 단어가 조건을 만족하며 그 길이가 3이기 때문입니다.
해결 접근 방식
이 문제는 동적 계획법(Dynamic Programming)을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 각 단어에 대해 '마지막 문자 하나를 뺀 부분 문자열'의 결과 값을 재활용하는 것입니다. 구체적인 단계는 다음과 같습니다.
- 먼저 리스트 w를 사전순으로 정렬합니다. 이렇게 하면 어떤 단어의 접두사가 항상 해당 단어보다 앞에 오게 되어 순차적으로 처리할 수 있습니다.
- dp := 딕셔너리(맵)를 생성하고, 존재하지 않는 키의 기본값은 0으로 설정합니다.
- res := 0으로 초기화하여 최종 결과를 저장할 준비를 합니다.
- w의 각 단어에 대해 다음을 반복합니다:
- dp[word] := dp[word의 마지막 문자를 제외한 부분 문자열] + 1
- res := res와 dp[word] 중 더 큰 값으로 갱신
- 모든 단어를 처리한 후 res를 반환합니다.
구현 예시
아래 Python 코드를 통해 위 로직을 더 명확하게 이해할 수 있습니다.
from collections import defaultdict
def solve(w):
w.sort()
dp = defaultdict(int)
res = 0
for word in w:
dp[word] = dp[word[:-1]] + 1
res = max(res, dp[word])
return res
w = ["pqr", "pq", "m", "mn", "pqrs"]
print(solve(w))
입력
["pqr", "pq", "m", "mn", "pqrs"]
출력
3
동작 원리 설명
위 코드에서 defaultdict(int)를 사용하면 아직 등장하지 않은 키에 접근할 때 자동으로 0이 반환되므로 별도의 초기화 처리가 필요 없습니다. 단어를 사전순으로 정렬했기 때문에, 예를 들어 "pqr"을 처리하는 시점에는 이미 그 접두사인 "pq"가 처리되어 dp["pq"] 값이 확정된 상태입니다. 따라서 dp[word[:-1]] + 1을 통해 현재 단어까지 이어지는 시퀀스의 길이를 바로 계산할 수 있습니다.
이 알고리즘의 시간 복잡도는 정렬에 O(n log n), 각 단어 처리에 평균적으로 O(k)(k는 단어 길이)가 소요되므로 전체적으로 매우 효율적입니다.