C++에서 S1의 접두사와 S2의 접미사를 이어 붙였을 때 회문이 되는 인덱스 i 찾기

개념

길이가 같은 두 문자열 S1과 S2가 주어졌을 때, S1[0…i]와 S2[i+1…n-1]을 이어 붙였을 때 회문(palindrome)이 되도록 하는 인덱스 i를 찾아야 합니다. 만약 조건을 만족하는 인덱스가 존재하지 않는다면 -1을 출력합니다.

입력 예시 1

S1 = "pqrsu", S2 = "wxyqp"

출력

1

S1[0..1] = "pq", S2[2..n-1] = "ypq"

S1 + S2 = "pqyqp"이며, 이는 회문입니다.

입력 예시 2

S1 = "pqrst", S2 = "qprqz"

출력

-1

접근 방법

• 먼저 0부터 n(문자열 길이)까지 반복하면서 S1의 i번째 문자를 새로운 문자열 S에 차례대로 추가합니다.
• 그다음 임시 문자열 temp를 만들고, S2의 i+1 인덱스부터 마지막(n-1)까지의 문자를 복사합니다.
• 마지막으로 두 문자열을 연결한 (S + temp)가 회문인지 검사하고, 회문이라면 현재 인덱스 i를 반환합니다.

C++ 구현 예제

// C++ 구현 코드
#include <bits/stdc++.h>
using namespace std;

// 문자열이 회문인지 확인하는 함수
bool isPalindrome(string str){
    int i = 0;
    int b = str.length() - 1;
    while (i < b) {
        if (str[i] != str[b])
            return false;
        i++;
        b--;
    }
    return true;
}

// 조건을 만족하는 인덱스를 반환하는 함수
int getIndex(string S1, string S2, int n){
    string S = "";
    for (int i = 0; i < n; i++) {
        // S1의 i번째 문자를 S에 추가
        S = S + S1[i];
        string temp = "";
        // S2의 i+1부터 끝까지의 문자를 temp에 복사
        for (int b = i + 1; b < n; b++)
            temp += S2[b];
        // 연결된 문자열이 회문인지 확인
        if (isPalindrome(S + temp)) {
            return i;
        }
    }
    return -1;
}

// 드라이버 코드
int main(){
    string S1 = "pqrsu", S2 = "wxyqp";
    int n = S1.length();
    cout << getIndex(S1, S2, n);
    return 0;
}

출력 결과

1

복잡도 분석

각 인덱스 i에 대해 문자열을 구성하고 회문 여부를 검사하는 데 O(n)의 시간이 소요되므로, 전체 시간 복잡도는 O(n²)입니다. 공간 복잡도는 임시 문자열을 저장하기 위해 O(n)입니다.