길이가 같은 두 문자열 S와 T가 주어졌을 때, 두 문자열을 같은 위치에서 잘라서 S의 앞부분과 T의 뒷부분을 이어 붙였을 때 회문(팰린드롬)이 되는지 확인하는 문제입니다.
예를 들어 입력이 S = "cat", T = "dac"라고 가정해 보겠습니다. 두 문자열을 각각 "c" + "at"과 "d" + "ac"로 자르면, S의 앞부분 "c"와 T의 뒷부분 "ac"를 합친 "cac"은 앞에서 읽으나 뒤에서 읽으나 같은 회문이므로 결과는 True가 됩니다.
알고리즘 접근 방식
이 문제는 다음 단계를 따라 해결할 수 있습니다.
n := 문자열 a의 길이로 설정
i := 0으로 초기화
i < n이면서 a[i]와 b[n-i-1]이 서로 같은 동안 i를 1씩 증가시킵니다. 이 과정은 두 문자열의 양 끝에서부터 안쪽으로 이미 회문 조건을 만족하는 부분의 길이를 측정하는 것입니다.
남은 중간 구간인 a[i ~ n-i-1] 또는 b[i ~ n-i-1] 중 하나라도 회문이라면 true를 반환합니다.
핵심 아이디어는 다음과 같습니다. 이미 대칭을 이루는 바깥쪽 부분은 그대로 사용하고, 가운데 남은 부분이 a 또는 b 어느 한쪽에서라도 회문이 성립하면 전체가 회문이 되기 때문입니다.
아래 구현 예시를 통해 더 자세히 이해해 보겠습니다.
예제 코드
class Solution:
def solve(self, a, b):
n = len(a)
i = 0
while i < n and a[i] == b[-i-1]:
i += 1
palindrome = lambda s: s == s[::-1]
return palindrome(a[i:n-i]) or palindrome(b[i:n-i])
ob = Solution()
S = "cat"
T = "dac"
print(ob.solve(S, T))
위 코드에서 s == s[::-1]은 파이썬의 슬라이싱 기법으로 문자열을 뒤집은 값과 원본을 비교하여 회문 여부를 판별하는 간결한 방법입니다.
입력
"cat","dac"
출력
True
이 알고리즘은 문자열 길이에 비례하는 O(n) 시간 복잡도로 동작하므로 매우 효율적입니다.