소문자로만 구성된 단어 목록이 주어졌을 때, 한 단어(word1)가 다른 단어(word2)의 선행자(predecessor)가 되는 조건은 word1의 아무 위치에 정확히 한 글자를 추가했을 때 word2와 같아지는 경우입니다. 예를 들어 "abc"는 "abac"의 선행자입니다.
단어 체인(word chain)은 [word_1, word_2, ..., word_k] 형태의 단어 시퀀스(k >= 1)로, word_1이 word_2의 선행자이고, word_2가 word_3의 선행자인 식으로 이어지는 구조를 말합니다. 우리의 목표는 주어진 단어 목록에서 선택한 단어들로 만들 수 있는 가장 긴 단어 체인의 길이를 구하는 것입니다.
예를 들어 입력이 ["a", "b", "ba", "bca", "bda", "bdca"]라면 결과는 4가 됩니다. ["a", "ba", "bda", "bdca"]가 가장 긴 체인 중 하나이기 때문입니다.
해결 접근 방식
이 문제는 동적 계획법(Dynamic Programming)과 해시 맵을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 각 단어에 대해, 그 단어에서 한 글자를 제거한 모든 부분 문자열을 만들어 봅니다.
- 제거된 문자열이 이미 처리된(더 짧은) 단어라면, 해당 단어까지의 최대 체인 길이에 1을 더한 값이 후보가 됩니다.
- 단어를 길이순으로 정렬해 두면, 짧은 단어부터 차례대로 처리할 때 필요한 dp 값이 항상 먼저 계산되어 있음을 보장할 수 있습니다.
알고리즘 단계
- dp 값을 저장할 맵(dp)을 정의하고, n := words 배열의 크기로 설정합니다.
- words 배열을 길이 기준으로 오름차순 정렬합니다.
- ret := 0으로 초기화합니다.
- i를 0부터 n-1까지 반복합니다.
- best := 0으로 초기화합니다.
- j를 0부터 words[i]의 길이 - 1까지 반복합니다.
- word := words[i]의 0~j-1 부분 문자열 + j+1부터 끝까지의 부분 문자열 (즉, j번째 문자 하나를 제거한 문자열)
- best := max(best, dp[word] + 1)
- dp[words[i]] := best
- ret := max(ret, dp[words[i]])
- ret을 반환합니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
static bool cmp(string s1, string s2){
return s1.size() < s2.size();
}
int longestStrChain(vector<string>& words) {
unordered_map <string, int> dp;
int n = words.size();
sort(words.begin(), words.end(), cmp);
int ret = 0;
for(int i = 0; i < n; i++){
int best = 0;
for(int j = 0; j < words[i].size(); j++){
string word = words[i].substr(0, j) +
words[i].substr(j + 1);
best = max(best, dp[word] + 1);
}
dp[words[i]] = best;
ret = max(ret, dp[words[i]]);
}
return ret;
}
};
main(){
vector<string> v = {"a","b","ba","bca","bda","bdca"};
Solution ob;
cout << (ob.longestStrChain(v));
}입력
["a","b","ba","bca","bda","bdca"]
출력
4
복잡도 분석
시간 복잡도는 O(N × L²)입니다. 여기서 N은 단어의 개수, L은 단어의 평균 길이입니다. 각 단어마다 L개의 부분 문자열을 생성하고, 각 문자열 생성에 O(L)의 비용이 들기 때문입니다. 공간 복잡도는 O(N × L)로, 해시 맵에 저장되는 단어들에 해당합니다.