길이가 같은 두 문자열 S1과 S2가 주어졌을 때, S1의 접두사와 S2의 접미사를 이어 붙였을 때 회문(palindrome)이 되도록 하는 인덱스 i를 찾는 문제입니다. 즉, S1[0...i]와 S2[i+1...n-1]를 연결한 결과가 앞뒤로 읽어도 같은 문자열이 되는 i를 구하고, 그런 인덱스가 존재하지 않으면 -1을 반환해야 합니다.
문제 예시
예를 들어 입력이 S1 = "pqrsu", S2 = "wxyqp"라고 가정해 보겠습니다. 이 경우 출력은 1입니다. S1[0..1] = "pq", S2[2..n-1] = "ypq"이고, 이 둘을 연결하면 "pqyqp"가 되는데, 이는 거꾸로 읽어도 동일한 회문이기 때문입니다.
해결 접근 방법
이 문제는 브루트 포스(완전 탐색) 방식으로 해결할 수 있습니다. 가능한 모든 인덱스 i에 대해 S1의 접두사와 S2의 접미사를 직접 만들어 보고, 연결한 문자열이 회문인지 검사하는 것입니다. 구체적인 단계는 다음과 같습니다.
- n := str1의 길이로 설정합니다.
- str := 빈 문자열로 초기화합니다.
- i를 0부터 n까지 반복합니다.
- str에 str1[i]를 하나씩 이어 붙입니다.
- temp := 빈 문자열로 초기화합니다.
- j를 i+1부터 n까지 반복하며 temp에 str2[j]를 이어 붙입니다.
- str과 temp를 연결한 문자열이 회문이면 현재 인덱스 i를 반환합니다.
- 모든 인덱스를 검사한 후에도 회문을 만들 수 없다면 -1을 반환합니다.
Python 구현 코드
아래 구현 예제를 통해 더 잘 이해해 보겠습니다.
def isPalindrome(s):
if s == s[::-1]:
return True
return False
def find_index(str1, str2):
n = len(str1)
str = ""
for i in range(n):
str = str + str1[i]
temp = ""
for j in range(i + 1, n):
temp += str2[j]
if (isPalindrome(str + temp)):
return i
return -1
str1 = "pqrsu"
str2 = "wxyqp"
print(find_index(str1, str2))입력
"pqrsu", "wxyqp"
출력
1
복잡도 분석
위 방법은 외부 반복문과 내부 반복문, 그리고 매번 회문 여부를 확인하는 과정 때문에 최악의 경우 O(n³)의 시간 복잡도를 가집니다. 따라서 입력 문자열이 짧은 경우에는 충분히 실용적이지만, 문자열 길이가 크다면 롤링 해시나 KMP 알고리즘을 활용한 최적화 기법을 고려하는 것이 좋습니다.