문자열을 거꾸로 뒤집어도 원래 문자열과 동일하게 유지된다면, 이를 회문(palindromic string)이라고 합니다.
이번 문제에서는 길이가 같은 두 문자열 'a'와 'b'가 주어집니다. 임의의 인덱스를 기준으로 두 문자열을 분할한 뒤, 분할된 부분들을 서로 조합했을 때 회문을 만들 수 있는지 확인하는 것이 과제입니다.
예를 들어 길이가 4인 두 문자열 'a'와 'b'를 인덱스 3에서 다음과 같이 분할했다고 가정해 보겠습니다.
aaa | b 와 bbb | a
이때 aaa(첫 번째 문자열의 접두사) + a(두 번째 문자열의 접미사)가 회문이어야 하며,
또는 b(첫 번째 문자열의 접미사) + bbb(두 번째 문자열의 접두사)가 회문이어야 합니다.
예제
입력-1:
a = "abcdef" b = "fedcba"
출력:
True
설명: 문자열 'a'와 'b'를 인덱스 2에서 분할하면 다음과 같이 됩니다.
abc | def 및 fed | cba
이때 abc(첫 번째 문자열의 접두사) + cba(두 번째 문자열의 접미사)가 "abccba"라는 회문을 이루므로 "True"를 반환합니다.
입력-2:
a = "eatable" b = "tableau"
출력:
False
설명: 어떤 인덱스로 분할하더라도 두 문자열을 조합해 회문을 만드는 방법은 존재하지 않습니다.
문제 해결 접근 방식
이 문제는 투 포인터(two-pointer) 기법을 활용하면 효율적으로 해결할 수 있습니다. 먼저 low와 high 두 개의 포인터를 초기화하는데, low는 문자열의 시작 위치(0)를, high는 마지막 문자의 위치를 가리키도록 합니다.
두 문자열의 길이가 같으므로, 먼저 문자열의 길이가 2보다 작은 경우에는 항상 True를 반환합니다. 그렇지 않다면 포인터를 이동시키면서 전체 문자열을 순회하며 재귀적으로 검사하고, 두 문자열이 회문 조건을 충족하면 True, 아니면 False를 반환합니다.
- 두 문자열 'a'와 'b'를 입력으로 받습니다.
- 부울 함수 checkPalindromic(string a, string b)는 두 문자열을 입력 매개변수로 받아 결과에 따라 True 또는 False를 반환합니다.
- 포인터 low는 0으로, high는 문자열의 마지막 인덱스로 초기화합니다.
- 양쪽 끝에서부터 포인터를 이동시켜 가며 두 문자열의 대응되는 문자들이 일치하는지 검사합니다.
- 부울 함수 Split(string a, string b)는 두 문자열을 조합해 회문을 만들 수 있으면 True, 그렇지 않으면 False를 반환합니다.
C++ 코드 구현
#include <bits/stdc++.h>
using namespace std;
bool isPalindrome(string a, int low, int high) {
while (low < high) {
if (a[low] != a[high])
return false;
low++;
high--;
}
return true;
}
bool Split(string a, string b) {
int low = 0;
int high = b.size() - 1;
while (low < high and a[low] == b[high]) {
low++;
high--;
}
return isPalindrome(a, low, high) || isPalindrome(b, low, high);
}
bool checkPalindromic(string a, string b) {
if (a.size() < 2)
return true;
return Split(a, b) || Split(b, a);
}
int main() {
string a = "abcpqr";
string b = "mnocba";
if (checkPalindromic(a, b)) {
cout << "True" << endl;
} else {
cout << "False" << endl;
}
return 0;
}위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
출력
True
설명: 주어진 문자열 'abcpqr'과 'mnocba'를 인덱스 2에서 분할하면 다음과 같습니다.
a(접두사) = abc 그리고 b(접미사) = cba
a(접미사) = pqr 그리고 b(접두사) = mno
여기서 a의 접두사 + b의 접미사, 즉 abc + cba는 "abccba"라는 회문을 이루므로 출력은 True입니다.
시간 복잡도
투 포인터 기법을 사용하면 각 문자열을 한 번씩만 순회하면 되므로, 전체 시간 복잡도는 문자열 길이에 비례하는 O(N)입니다. 공간 복잡도 역시 추가 배열 없이 포인터만 사용하므로 O(1)로 매우 효율적입니다.