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