회문 작성 알고리즘

회문 작성 알고리즘이란?

한 문장을 앞에서부터 읽은 것이나, 뒤에서부터 읽은 것이나 같은 문장

예시 : abcdedcba 

문제 

: 문자열로 들어오는 str 뒤에 0 이상의 값을 추가하여 회문을 생성하고자 한다.

생성할 수 있는 가장 짧은 회문의 길이를 구하시오.

아이디어 짜기

1. 구하는 값은 str의 총 길이가 될 것이며, str 뒤에 0 이상의 값을 추가하여 회문을 만드는 것이기 때문에

리턴되는 회문의 최단 길이는 str의 길이가 될 것입니다.

따라서 구하려는 값의 초기 값은 str의 길이로 잡고 시작하면 됩니다.

2. 비교할 것은 문자열의 처음 위치 값과 그 다음 위치 값을 비교합니다. 

3. 다른 값이 나올 경우 반복문을 끝내고 회문이 아니기 떄문에 str 문자열 뒤에 값을 추가합니다.

코드는 다음과 같습니다.

---

public static void main(String[] args) {

// TODO Auto-generated method stub

System.out.print(find("abcdefabcdef"));

}

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;

}

}

}

}

---

i값은 str 문자열의 길이가 되고, j는 초기 문자열의 인덱스부터 비교하고자 쭉쭉 치고나가는 값입니다.

또한 str 문자열의 마지막 인덱스부터 하나씩 내려오면서 비교해야 하므로 (i-j-1)로 잡아서 진행했습니다.

만일 그 비교하는 값이 다르다면 flag를 false로 두고 내부 반복문을 깨서 다시 문자열 하나를 더 증가시켜

회문이 되는지를 다시 확인합니다.

만일 회문이라면, flag는 true로 남게되고, 내부 반복문도 끝나게 되어 마지막 i 값 (결과적으로 str의 최종 문자열 길이)이 반환됩니다.

바로 리턴해줘야만 최단 길이가 되기 때문에 다음과 같이 하였으며,

최종 결과값인 str의 문자열 길이가 main함수에서 출력되게 됩니다.

이상 회문 만들기 알고리즘 풀이였습니다.

감사합니다.