C++ 문자 교체 쿼리 처리 후 회문 여부 확인하기

문제 개요

하나의 문자열과 쿼리 집합 Q가 주어져 있다고 가정해 봅시다. 각 쿼리는 두 개의 정수 i와 j, 그리고 하나의 문자 c로 구성됩니다. 우리는 문자열에서 인덱스 i와 j에 위치한 문자들을 새로운 문자 c로 교체한 후, 그 문자열이 회문(palindrome)인지 아닌지를 판별해야 합니다.

예를 들어 문자열이 "AXCDCMP"라고 해보겠습니다. 첫 번째 쿼리로 (1, 5, 'B')를 수행하면 문자열은 "ABCDCBP"가 됩니다. 이어서 두 번째 쿼리로 (0, 6, 'A')를 수행하면 문자열은 "ABCDCBA"가 되는데, 이 문자열은 앞에서 읽으나 뒤에서 읽으나 같은 회문입니다.

정리하면, 인덱스 i와 j를 받아 해당 위치의 문자들을 c로 교체한 뒤 회문 여부를 확인하는 쿼리 처리 프로그램을 작성하는 것이 목표입니다.

C++ 구현 예제

#include <iostream>
using namespace std;
class Query{
    public:
    int i, j;
    char c;
    Query(int i, int j, char c){
        this->i = i;
        this->j = j;
        this->c = c;
    }
};
bool isPalindrome(string str){
    int n = str.length();
    for (int i = 0; i < n/2 ; i++)
    if (str[i] != str[n-1-i])
        return false;
        return true;
}
bool palindromeAfterQuerying(string str, Query q[], int n){
    for(int i = 0; i<n; i++){
        str[q[i].i] = q[i].c;
        str[q[i].j] = q[i].c;
        if(isPalindrome(str)){
            cout << str << " is Palindrome"<< endl;
        }else{
            cout << str << " is not Palindrome"<< endl;
        }
    }
}
int main() {
    Query q[] = {{1, 5, 'B'}, {0, 6, 'A'}};
    int n = 2;
    string str = "AXCDCMP";
    palindromeAfterQuerying(str, q, n);
}

실행 결과

ABCDCBP is not Palindrome
ABCDCBA is Palindrome

코드 동작 원리

위 코드의 핵심 구성 요소를 살펴보겠습니다.

• Query 클래스: 각 쿼리의 정보인 인덱스 i, j와 교체할 문자 c를 저장합니다.
• isPalindrome 함수: 문자열 길이의 절반만큼만 반복하면서 앞쪽 문자와 뒤쪽 대칭 위치의 문자를 비교합니다. 하나라도 다르면 false를 반환하고, 모두 일치하면 true를 반환합니다. 시간 복잡도는 O(n)입니다.
• palindromeAfterQuerying 함수: 주어진 쿼리 배열을 순차적으로 순회하며, 각 쿼리마다 인덱스 i와 j의 문자를 c로 교체한 후 isPalindrome 함수를 호출해 결과를 출력합니다.

실행 과정을 단계별로 보면, 먼저 초기 문자열 "AXCDCMP"에 첫 번째 쿼리 {1, 5, 'B'}가 적용되어 인덱스 1의 'X'와 인덱스 5의 'P'가 'B'로 바뀌면서 "ABCDCBP"가 됩니다. 이 문자열은 양 끝의 'A'와 'P'가 서로 다르므로 회문이 아니라고 출력됩니다. 이후 두 번째 쿼리 {0, 6, 'A'}가 적용되면 인덱스 0의 'A'와 인덱스 6의 'P'가 'A'로 바뀌어 "ABCDCBA"가 되고, 이 문자열은 좌우 대칭이므로 회문이라고 출력됩니다.

이 접근 방식은 각 쿼리마다 전체 문자열을 처음부터 검사하므로 직관적이고 이해하기 쉽습니다. 문자열의 길이를 n, 쿼리의 개수를 m이라 할 때 전체 시간 복잡도는 O(m × n)이 됩니다.