CodeWars 예순 일곱 번째 문제

longest_palindrome

public static int longestPalindrome(final String s) {
    String original = s;
    //String original = s.replace(" ", ""); /// 1번

    for(int i = original.length(); i >= 1 ; i--) {

        for(int j = 0; j <= original.length() - i; j++) {

            if(isPalindrome(original.substring(j, j+i))){
                return i;
            }

            /*
				if(reverse.contains(original.substring(j, j+i))){ /// 2번
					return i;
				}
				*/
        }
    }

    return 0;
}

private static boolean isPalindrome(String substring) {
    String reverse = new StringBuilder(substring).reverse().toString();

    return reverse.equals(substring);
}

• 이 문제는 처음 잘못된 접근법과 추후 다시 생각하여 올바른 접근에도 잘못된 해석으로 인하여 탈이 많았다.
• 일단 회문을 기본적으로 물어보는 문제로서 학창시절 한 번씩 접해보는 문제다.
• 나는 문자를 뒤집어서 기존의 문자열과 한개, 두개 비교해 나가서 가장 큰 회문을 찾으려고 했다.
• 그러나 그것은 효율적이지 않다. greddy 알고리즘에 더 가깝게 원 문자열 크기부터 줄여나가는 방식으로 찾았다. 다시 그러나…
• 1번의 경우 띄어쓰기에 대해서는 회문에 대하여 포함하냐 안하냐에서 나는 포함을 하지 않는 줄 알았다. 그러나 포함하더라… 해석이 잘못 되었다.
• 2번의 경우 내가 오해를 한 것이 zabcaz의 경우 회문이 아니기 때문에 1이 나와야 한다. 그러나 2번 처럼 contain을 쓸 경우 2가 나온다. 왜냐하면 reverse를 하면 zacbaz가 나오는데 za가 겹치기 때문이다. (az는 나중에 검색되는 경우 아니 검색하기 전 이미 za에서 return되므로 경우의 수에 없다).
• 결론적으로 2번은 아주 잘못된 접근 법이다.
• 이렇게 겨우 문제를 해결하였다.