Palindrome, 팰린드롬(회문) 만들기 - 1부

이 포스팅은 Shubham Chaudhary 가 작성한 문서를 참조해서 작성했습니다.

문제

문자열 s 가 주어졌을때 s에 문자를 붙여서 (끝 부분에 삽입한다 생각) 회문(palindrome)을 만들 수 있는 최소의 문자 갯수를 찾아라.

예시

Input : s = "abede"
Output : 2

"abedeba" 로 회문을 만들 수 있습니다. 끝에 ba 를 추가했습니다.

Input : s = "aabb"
Output : 2

"aabbaa" 로 회문을 만들 수 있습니다. 끝에 aa 를 추가했습니다.

---

정답

문제와 달리 정답은 정 반대로 접근합니다.

솔루션은 다음과 같습니다 :
문자열의 가장 처음부터 하나씩 제거하고 그 문자열이 회문인지 확인합니다.

예를 들자면, 문자열 s = "abede" 을 생각해보세요.

처음엔 일단 주어진 문자열이 회문인지 아닌지 검사합니다.

만약 회문이 아니라면, 문자열중에 가장 첫번째 문자를 지웁니다.
이렇게 되면 문자열 s 는 "bede" 가 됩니다.

이제 또 문자가 회문인지 아닌지 검사합니다. 회문이 아니라면, 문자열중에 가장 첫번째 문자를 지웁니다.
이렇게 되면 문자열 s 는 "ede" 가 됩니다.

이제는 눈으로 봐도 문자열이 회문인지 알 수 있습니다.
즉, 처음 문자열 s 에서 회문이 되기위해 붙여야 하는 최소 문자 개수는 2개 입니다.

아래는 C 로 작성한 솔루션 입니다.

// 회문이 되기위해 붙여야 하는 최소 문자 개수를 찾는 C 프로그램
#include<stdio.h>
#include<string.h>
#include<stdbool.h>

// 문자열이 회문인지 아닌지 검사한다.
bool isPalindrome(char *str)
{
    int len = strlen(str);

    // 1개의 문자는 언제나 회문입니다.
    if (len == 1)
        return true;

    // 첫번째 문자의 pointer를 가져옴
    char *ptr1 = str;

    // 마지막 문자의 pointer를 가져옴.
    char *ptr2 = str+len-1;

    while (ptr2 > ptr1)
    {
        if (*ptr1 != *ptr2)
            return false;
        ptr1++;
        ptr2--;
    }

    return true;
}

// 붙여야 하는 문자를 세는 재귀 함수
int noOfAppends(char s[])
{
    if (isPalindrome(s))
        return 0;

    // 포인터 주소값을 증가시켜서
    // 문자열의 첫번째 문자를 제거한다. 
    s++;

    return 1 + noOfAppends(s);
}

// 테스트를 위한 드라이버 프로그램
int main()
{
    char s[] = "abede";
    printf("%d\n", noOfAppends(s));
    return 0;
}

출력값

2

---

조금 더 어려운 회문 문제를 곧 포스팅 하도록 하겠습니다.