팰린드롬(palindrome)은 거꾸로 읽어도 제대로 읽는 것과 같은 문장이나 낱말을 뜻합니다.
평소 팰린드롬을 굉장히 좋아하던 김팰린은 아무 단어나 입력해도 팰린드롬으로 만들어주는 인공지능인 '팰파고'를 만들고자 합니다.
팰파고의 기능은 다음과 같습니다.
팰린드롬을 만들 수 있는 단어가 입력되면 단어의 알파벳 순서를 재배열하여 팰린드롬을 만듭니다. 이 때, 대칭이 되는 왼쪽 부분을 알파벳 순서로 정렬합니다. (단어의 길이가 홀수일 경우엔 중심을 포함한 대칭 왼쪽 부분을 알파벳 순서로 정렬합니다.) 예를 들어, BAACBC가 입력되면 ABCCBA를 만들어 줍니다.
팰린드롬을 만들 수 없는 단어가 입력되면 필요한 최소한의 알파벳을 추가하여 팰린드롬을 만들어줍니다. 이 때, 역시 대칭이 되는 왼쪽 부분을 알파벳 순서로 정렬해줍니다. 예를 들어, BACBAD가 입력되면 ABCDCBA를 만들어줍니다.