팰린드롬 만들기

앞서 팰린드롬 여부를 파악했던 DP문제를 풀었다면, 이번에는 팰린드롬을 만드는 알고리즘을

구현해보겠습니다.

만약 입력한 내용이 이미 팰린드롬 형태라면 해당 입력된 문자열의 길이가

출력될 것이며, 팰린드롬이 아닌 경우에는, 입력한 내용이 팰린드롬이 될 경우 얼마 만큼의 

문자열의 길이가 정의되는지 출력될 것입니다.

코드는 상당히 짧기 때문에 먼저 전체 코드를 보여주고 설명하도록 하겠습니다.

---

package algorithm;

import java.util.Scanner;

public class ThePalindrome {

private static Scanner scanner;

private static String s;

public static void main(String[] args) {

// TODO Auto-generated method stub

scanner = new Scanner(System.in);

s = scanner.nextLine().trim();

System.out.print(find(s));

}

public static int find(String str) {

for (int i = str.length();; i++) {

boolean flag = true;

for (int j = 0; j < str.length(); j++) {

if ((i - j - 1) < str.length() && str.charAt(j) != str.charAt(i - j - 1)) {

flag = false;

break;

}

}

if (flag) {

return i;

}

}

}

}

---

첫 반복문에서는 입력되는 문자열의 길이부터 값을 시작합니다.

두 번째 반복문을 확인할 경우 왜 첫 반복문에서 문자열의 길이부터 값을 시작하는지 알 수 있습니다.

우선 문자열의 길이나 배열의 길이, 미로 문제 등 무언가 이동하는 문제일 경우에는 반드시

돌아다닐 수 있는 범위 내에서 진행되어야 합니다.

if ((i - j - 1) < str.length() && str.charAt(j) != str.charAt(i - j - 1))

따라서 (i-j-1) < str.length()라는 조건을 둔 것입니다.

이 후 에는 j값에 대한 문자열의 위치(char)에 대한 값과 문자열의 마지막 위치에 대한 값을 비교합니다.

같지 않을 경우 팰린드롬이 아니라고 판단하여 flag는 false를 주고 안 쪽 반복문을 벗어납니다.

이렇게 여러 번의 과정을 거친 다음에 팰린드롬이 계속해서 아닐 경우라면 문자열의 마지막 값에서

반복문이 모두 종료되면서 위치 값인 i가 출력될 것입니다.

그 말인 즉, 해당 문자열 만큼 팰린드롬을 만들기 위해서 인덱스(i) 값이 커졌다는 걸 반증합니다.

예를 들어, ABCDE 라는 문자열을 입력했다고 가정해봅시다.

그럴 경우, 안 쪽 반복문이 break를 반복하면서 i 값은 계속해서 증가할 것이고, 결국 E를 남겨두고 

flag는 true 값을 갖고 해당 위치인 i 값이 출력될 것입니다.

이는 직접적으로 팰린드롬을 만드는 것은 아니지만, ABCDE가 팰린드롬이 되기 위해서는

ABCDE(DCBA) 이렇게 4개의 수를 추가해줘서 총 9라는 자릿값이 반환될 것임을 알 수 있습니다.

만일 입력 값이 팰린드롬일 경우 처음부터 flag가 true가 될 것이기 때문에 바로 해당 입력 값의 

문자열의 길이가 반환될 것입니다. 

감사합니다.