이 튜토리얼에서는 문자를 최대 하나만 변경하여 주어진 문자열을 회문(palindrome)으로 만들 수 있는지 판단하는 프로그램을 다룹니다.
회문이란 앞에서부터 읽으나 뒤에서부터 읽으나 동일한 문자열을 의미합니다. 예를 들어 "abba", "level"처럼 좌우가 대칭을 이루는 문자열이 대표적인 회문입니다.
문제 정의
하나의 문자열이 주어졌을 때, 단 한 글자만 수정해서 이 문자열을 회문으로 바꿀 수 있는지 확인하는 것이 목표입니다. 이미 회문인 경우에도 변경 없이 조건을 만족하므로 "Yes"를 출력해야 합니다.
접근 방법
핵심 아이디어는 매우 간단합니다.
1. 양쪽 끝에서 중앙으로 비교
문자열의 첫 번째 문자와 마지막 문자, 두 번째 문자와 뒤에서 두 번째 문자를 차례대로 비교하며 중앙까지 진행합니다.
2. 불일치 개수 세기
서로 다른 문자 쌍이 발견될 때마다 카운트를 증가시킵니다. 이 불일치 지점은 한 문자를 변경하면 대칭을 맞출 수 있습니다.
3. 조건 판정
불일치 개수가 1 이하라면 한 번의 변경(또는 변경 없이)으로 회문을 만들 수 있으므로 true를 반환하고, 그렇지 않으면 false를 반환합니다.
이 알고리즘은 문자열 길이의 절반만 순회하므로 시간 복잡도는 O(n), 공간 복잡도는 O(1)로 매우 효율적입니다.
C++ 구현 예제
#include<bits/stdc++.h>
using namespace std;
// 한 문자 변경으로 회문 변환이 가능한지 검사하는 함수
bool if_palindrome(string str){
int n = str.length();
// 변경이 필요한 문자 개수를 저장할 변수
int count = 0;
for (int i = 0; i < n/2; ++i)
if (str[i] != str[n - i - 1])
++count;
return (count <= 1);
}
int main(){
string str = "abccaa";
if (if_palindrome(str))
cout << "Yes" << endl;
else
cout << "No" << endl;
return 0;
}실행 결과
Yes
동작 원리 분석
예제 문자열 "abccaa"를 살펴보겠습니다.
- 첫 번째 비교: str[0]('a') vs str[5]('a') → 일치
- 두 번째 비교: str[1]('b') vs str[4]('a') → 불일치 (count = 1)
- 세 번째 비교: str[2]('c') vs str[3]('c') → 일치
불일치가 한 곳뿐이므로 'b'를 'a'로 변경하면 "aaccaa"가 되어 회문이 됩니다. 따라서 결과는 "Yes"입니다.
반면 불일치 쌍이 두 개 이상이라면 한 번의 변경으로는 해결할 수 없어 "No"가 출력됩니다. 이 방식은 문자열 검증, 데이터 정합성 확인 등 다양한 실무 상황에서 활용할 수 있는 기본적이면서도 유용한 패턴 매칭 기법입니다.