문제 개요
중복 없는 서로 다른 단어들의 목록이 주어져 있습니다. 우리가 설계해야 할 알고리즘은 이 목록 속에서 연결된 단어(concatenated word)를 모두 찾아내는 것입니다. 여기서 연결된 단어란 주어진 배열에 포함된 두 개 이상의 더 짧은 단어만으로 완전히 구성된 문자열을 의미합니다.
예를 들어 단어 목록이 ["cow", "cows", "cowsgoatcows", "goat", "goatcowsgoat", "hippopotamuses", "deer", "deercowgoatcow"]라고 가정하면, 출력 결과는 ["cowsgoatcows", "goatcowsgoat", "deercowgoatcow"]가 됩니다.
- "cowsgoatcows" = "cows" + "goat" + "cows"
- "goatcowsgoat" = "goat" + "cows" + "goat"
- "deercowgoatcow" = "deer" + "cow" + "goat" + "cow"
문제 해결 접근법
이 문제는 트라이(Trie) 자료구조와 메모이제이션(Memoization)을 함께 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 단어들을 길이순으로 정렬한 뒤, 짧은 단어부터 차례대로 처리합니다.
- 각 단어에 대해, 지금까지 처리된 단어들이 저장된 트라이에서 현재 단어를 만들 수 있는지 확인합니다.
- 만들 수 있다면 연결된 단어이므로 결과에 추가하고, 만들 수 없다면 트라이에 새로 삽입합니다.
- 이 순서 덕분에 어떤 단어를 검사하는 시점에는 항상 자신보다 짧은 단어들만 트라이에 존재하게 되므로, "최소 두 개의 단어로 구성되어야 한다"는 조건이 자연스럽게 충족됩니다.
1. isPresent() 함수 — 단어 분해 가능 여부 확인
isPresent() 함수는 문자열 str, 트라이의 루트 노드 head, 시작 위치 idx, 메모이제이션용 dp 배열을 인자로 받습니다.
- 기저 조건: idx가 str의 길이보다 크거나 같으면 문자열 끝까지 성공적으로 분해한 것이므로 true를 반환합니다.
- 메모이제이션 확인: dp[idx]가 -1이 아니라면 이미 계산된 값이므로 즉시 반환하여 중복 연산을 피합니다.
- 탐색용 노드 curr를 루트로 초기화하고 결과 변수 ok를 false로 설정합니다.
- idx부터 문자열 끝까지 한 글자씩 진행하며 다음을 수행합니다.
- 현재 문자 x에 대응하는 자식 노드가 없으면 탐색을 중단(break)합니다.
- 자식 노드가 있으면 curr를 해당 자식 노드로 이동합니다.
- 이동한 노드가 단어의 끝(isEnd)이라면, 남은 부분(i+1부터)에 대해 재귀적으로 isPresent()를 호출하고 그 결과를 ok에 OR 연산으로 누적합니다.
- 최종적으로 dp[idx]에 ok를 저장한 뒤 반환합니다.
2. insertNode() 함수 — 트라이에 단어 삽입
- curr를 루트 노드로 설정합니다.
- 단어 s의 각 문자에 대해 해당 자식 노드가 없으면 새 Node를 생성하고, curr를 자식 노드로 이동시킵니다.
- 마지막 문자에 도달한 노드의 isEnd 값을 true로 설정하여 단어의 끝임을 표시합니다.
3. 메인 로직 흐름
- 루트 노드 head를 생성합니다.
- 단어 배열 words를 길이 기준으로 오름차순 정렬합니다.
- 결과를 저장할 배열 ret를 준비합니다.
- 각 단어에 대해 다음을 수행합니다.
- 빈 문자열이면 건너뜁니다.
- 단어 길이와 같은 크기의 dp 배열을 -1로 초기화합니다.
- isPresent() 호출 결과가 참이면 ret에 해당 단어를 추가합니다.
- 그렇지 않으면 insertNode()를 호출해 트라이에 삽입합니다.
- 모든 단어를 처리한 후 ret를 반환합니다.
C++ 전체 구현 코드
다음 구현 예제를 통해 동작 방식을 더 잘 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
struct Node{
bool isEnd;
map <char, Node*> child;
Node(){
isEnd = false;
}
};
class Solution {
public:
bool isPresent(string str, Node* head, int idx, vector <int>& dp){
if(idx >= str.size())return true;
if(dp[idx] != -1)return dp[idx];
Node* curr = head;
bool ok = false;
for(int i = idx; i < str.size(); i++){
char x = str[i];
if(!curr->child[x]){
break;
}else{
curr = curr->child[x];
}
if(curr->isEnd){
ok |= isPresent(str, head, i + 1, dp);
}
}
return dp[idx] = ok;
}
static bool cmp(string s1, string s2){
return s1.size() < s2.size();
}
void insertNode(Node* head, string s){
Node* curr = head;
for(int i = 0; i < s.size(); i++){
char x = s[i];
if(!curr->child[x]){
curr->child[x] = new Node();
}
curr = curr->child[x];
}
curr->isEnd = true;
}
vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
Node* head = new Node();
sort(words.begin(), words.end(), cmp);
vector <string> ret;
for(int i = 0; i < words.size(); i++){
string curr = words[i];
if(curr=="")continue;
vector <int> dp(curr.size(), -1);
if(isPresent(curr, head, 0, dp)){
ret.push_back(curr);
}else{
insertNode(head, curr);
}
}
return ret;
}
};
main(){
Solution ob;
vector<string> v = {"cow","cows","cowsgoatcows","goat","goatcowsgoat","hippopotamuses","deer","deercowgoatcow"};
print_vector(ob.findAllConcatenatedWordsInADict(v));
}
입력 및 실행 결과
입력
{"cow","cows","cowsgoatcows","goat","goatcowsgoat","hippopotamuses","deer","deercowgoatcow"}
출력
[cowsgoatcows, goatcowsgoat, deercowgoatcow]
시간 복잡도 분석
각 단어의 분해 가능 여부를 확인하는 데는 O(L²)의 시간이 걸립니다(L은 단어 길이). 따라서 전체 시간 복잡도는 대략 O(N × L²)입니다(N은 단어 개수). 메모이제이션 덕분에 같은 시작 위치에 대한 중복 탐색이 제거되므로, 단순 재귀 방식에 비해 실제 실행 성능이 크게 향상됩니다.