사전(단어 집합)과 하나의 문자열 s가 주어졌을 때, 문자열 s의 일부 문자를 삭제하여 만들 수 있는 사전 내 최장 단어를 찾는 것이 이번 문제의 목표입니다. 이때 중요한 조건은 삭제한 뒤 남은 문자들의 상대적인 순서가 그대로 유지되어야 한다는 점입니다. 즉, 답이 되는 단어는 반드시 문자열 s의 부분 수열(subsequence)이어야 합니다.
예를 들어 문자열 s가 "apbreoigroakml"이고, 사전에 {"prog", "ram", "program"}이 저장되어 있다고 가정해 보겠습니다. 세 단어 모두 s의 부분 수열이 될 수 있지만, 그중 길이가 가장 긴 단어는 "program"이므로 최종 결과는 "program"이 됩니다.
문제 해결 접근 방법
이 문제는 다음과 같은 순서로 해결할 수 있습니다.
- 사전의 모든 단어를 하나씩 순회합니다.
- 각 단어가 문자열 s의 부분 수열인지 두 포인터(two pointer) 기법으로 확인합니다.
- 부분 수열이면서 지금까지 찾은 최장 단어보다 길다면 결과 단어와 길이를 갱신합니다.
- 모든 단어를 검사한 뒤 최종 결과를 반환합니다.
부분 수열 판별 함수 isSubSequence
isSubSequence 함수는 문자열 s1이 s2의 부분 수열인지 검사합니다. s2를 처음부터 끝까지 훑으며 s1의 문자와 일치할 때마다 포인터 j를 증가시키고, 반복이 끝난 후 j가 s1의 길이와 같다면 s1의 모든 문자가 s2 안에서 순서대로 존재한다는 의미이므로 true를 반환합니다.
C++ 예제 코드
#include<iostream>
#include<vector>
using namespace std;
// s1이 s2의 부분 수열인지 확인하는 함수
bool isSubSequence(string s1, string s2) {
int m = s1.length(), n = s2.length();
int j = 0;
for (int i = 0; i < n && j < m; i++)
if (s1[j] == s2[i])
j++;
return (j == m);
}
// 사전에서 s의 부분 수열이 되는 가장 긴 단어를 찾는 함수
string getLongestSubstr(vector<string> dict, string s) {
string result = "";
int length = 0;
for (string word : dict) {
if (length < word.length() && isSubSequence(word, s)) {
result = word;
length = word.length();
}
}
return result;
}
int main() {
vector<string> dict = {"prog", "ram", "program"};
string str = "apbreoigroakml";
cout << getLongestSubstr(dict, str) << endl;
}실행 결과
program
시간 및 공간 복잡도
사전에 N개의 단어가 있고 문자열 s의 길이를 n이라 할 때, 각 단어에 대한 부분 수열 검사에는 O(n)의 시간이 걸립니다. 따라서 전체 시간 복잡도는 O(N × n)이며, 별도의 추가 메모리 없이 포인터 변수만 사용하므로 공간 복잡도는 O(1)입니다.