문제 소개
비어 있지 않은 문자열이 하나 주어집니다. 이때 해당 문자열을 자기 자신의 부분 문자열 하나를 골라 여러 번 이어 붙여서 만들 수 있는지 확인해야 합니다. 문자열은 소문자 영어 알파벳으로만 구성되며, 길이는 10,000을 넘지 않는다고 가정합니다.
예를 들어 입력이 "abaabaaba"라면 정답은 true입니다. 이 문자열은 "aba"를 세 번 반복하여 만들 수 있기 때문입니다.
풀이 접근 방식
이 문제는 KMP 알고리즘에 사용되는 실패 함수, 즉 LPS(Longest Proper Prefix which is also Suffix) 배열을 응용한 동적 프로그래밍(DP)으로 효율적으로 해결할 수 있습니다. 단계별 과정은 다음과 같습니다.
- 동적 프로그래밍 접근 방식을 사용합니다.
- 문자열 길이와 같은 크기 n의 DP 배열을 선언합니다.
- i := 1, j := 0으로 초기화합니다.
- i < n인 동안 아래를 반복합니다.
- str[i] == str[j]라면 DP[i] := j + 1로 설정하고, i와 j를 각각 1씩 증가시킵니다.
- 일치하지 않는 경우,
- j > 0이면 j := DP[j - 1]로 되돌립니다.
- 그렇지 않다면 dp[i] := 0으로 설정하고 i를 1 증가시킵니다.
- DP[n - 1]이 0이 아니고, n % (n - DP[n - 1]) == 0을 만족하면 true를 반환합니다.
- 그 외의 경우에는 false를 반환합니다.
핵심 아이디어는 다음과 같습니다. LPS 배열의 마지막 값은 문자열 전체에서 '접두사이면서 동시에 접미사'가 될 수 있는 가장 긴 부분의 길이를 의미합니다. 따라서 n이 (n - LPS[n-1]) 값으로 나누어떨어진다면, 문자열은 길이 (n - LPS[n-1])짜리 패턴이 반복된 형태라고 확신할 수 있습니다.
C++ 구현 예제
아래 코드를 통해 실제 구현을 살펴보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool repeatedSubstringPattern(string s) {
int n = s.size();
vector<int> dp(n);
int i = 1;
int j = 0;
while(i < n){
if(s[i] == s[j]){
dp[i] = j + 1;
i++;
j++;
} else {
if(j > 0){
j = dp[j - 1];
} else {
dp[i] = 0;
i++;
}
}
}
return dp[n - 1] != 0 && n % (n - dp[n - 1]) == 0;
}
};
int main(){
Solution ob;
string res = ob.repeatedSubstringPattern("abaabaaba") ? "true" : "false";
cout << res;
return 0;
}입력
"abaabaaba"
출력
true
복잡도 분석
시간 복잡도는 O(n)입니다. 문자열을 한 번만 순회하면서 LPS 배열을 채우기 때문입니다. 공간 복잡도 역시 LPS 배열을 저장하기 위해 O(n)이 필요합니다. 이 방식은 단순히 모든 가능한 부분 문자열을 시도하는 브루트 포스(O(n²))보다 훨씬 효율적이므로, 길이가 최대 10,000인 입력에서도 안정적으로 동작합니다.