두 개의 문자열 str1과 str2가 주어졌다고 가정해 봅시다. 두 번째 문자열(str2)에 0회 이상의 연산을 수행한 뒤, 두 문자열 사이에서 가장 긴 공통 접두사(longest common prefix)를 찾는 것이 목표입니다. 여기서 각 연산은 str2 내에서 임의의 두 문자를 서로 맞바꾸는 것입니다.
예를 들어 str1 = "HERE", str2 = "THERE"인 경우를 살펴보겠습니다. str2의 문자들을 적절히 교환하여 "HERET"으로 만들면, 두 문자열의 공통 접두사 길이는 4가 됩니다.
접근 방법
문자 교환은 오직 str2에서만 가능하며, 공통 접두사의 길이는 최대한 길게 만들어야 합니다. 이를 해결하기 위한 핵심 아이디어는 다음과 같습니다.
- 먼저 str2의 각 문자별 빈도수를 크기 26의 배열에 저장합니다(소문자 기준).
- 그다음 str1을 앞에서부터 순회하면서, 현재 문자가 str2에 아직 남아 있는지(빈도수가 0보다 큰지) 확인합니다.
- 남아 있다면 해당 문자의 빈도수를 1 감소시키고 접두사 길이를 1 증가시킨 뒤 다음 문자로 진행합니다.
- 더 이상 사용할 수 없는 문자를 만나면 순회를 중단하고, 지금까지 매칭된 str1 부분의 길이를 결과로 출력합니다.
이 방식이 올바르게 동작하는 이유는, str2의 문자들은 어떤 위치로든 자유롭게 재배치될 수 있기 때문에 str1의 접두사를 구성하는 데 필요한 문자들이 str2 전체에 충분히 존재하기만 하면 되기 때문입니다.
예제 코드
#include <iostream>
using namespace std;
void longestPrefix(string str1, string str2) {
int frequency[26]={0};
int a = str1.length();
int b = str2.length();
for (int i=0 ;i<b ; i++) {
frequency[str2[i] - 97] += 1;
}
int c = 0;
for (int i=0 ;i<a ; i++) {
if (frequency[str1[i] - 97] > 0){
c += 1;
frequency[str1[i] - 97] -= 1;
} else
break;
}
cout<<"Length of longest common prefix: " << c;
}
int main() {
string str1="here", str2 = "there";
longestPrefix(str1, str2);
}출력 결과
Length of longest common prefix: 4
시간 복잡도 분석
위 알고리즘은 먼저 str2를 한 번 순회하여 빈도수를 계산하고(O(b)), 이후 str1을 한 번 순회하면서 접두사를 확인하므로(O(a)), 전체 시간 복잡도는 O(a + b)입니다. 여기서 a와 b는 각각 str1과 str2의 길이입니다. 또한 추가로 사용되는 빈도수 배열은 알파벳 소문자 개수에 해당하는 상수 크기(26)이므로 공간 복잡도는 O(1)입니다.