회문을 찾는 여러 방법(Check if a String Is a Palindrome in Java)

원본 글: https://www.baeldung.com/java-palindrome

회문이란, 문자열을 앞으로 읽었을때나 뒤로 읽었을때 똑같은 문자열을 말한다. 예를들어 "madam", "racecar", "토마토", "기러기" 등이 있다.

1. Check if a String Is a Palindrome

1.1 A Simple Approach

단순하게 반복문을 돌아서 회문인지 확인합니다.

    @Test
    public void java_core_test() {
        Assertions.assertTrue(isPalindrome("racecar"));
    }

    private static boolean isPalindrome(String text) {
        String clean = text.replaceAll("\\s+", "").toLowerCase();
        int length = clean.length();
        int forward = 0;
        int backward = length - 1;
        while (forward < backward) {
            char forwardChar = clean.charAt(forward++);
            char backwardChar = clean.charAt(backward--);
            if(forwardChar != backwardChar) {
                return false;
            }
        }
        return true;
    }

문자열 앞, 뒤로 반복문을 돌면서 문자가 일치하지 않는 경우 return값을 false로 둡니다.

1.2 Reversing the String

비교할 문자열을 뒤집어서 비교대상 문자열과 비교하는 방법이 있습니다.

    @Test
    public void reversing_text_test() {
        Assertions.assertTrue(isPalindromeReverseTheString("racecar"));
    }

    private static boolean isPalindromeReverseTheString(String text) {
        StringBuilder reverse = new StringBuilder();
        String clean = text.replaceAll("\\s+", "");
        char[] plain = clean.toCharArray();
        for(int i = plain.length - 1; i >= 0; i--) {
            reverse.append(plain[i]);
        }
        return text.equals(reverse.toString());
    }

문자열을 뒤집는 reverse()함수를 사용하지 않았습니다.
이를 사용하여 보기 좋게 재작성 해보겠습니다.

    private static boolean isPalindromeUsingStringBuilder(String text) {
        String clean = text.replaceAll("\\s+", "");
        StringBuilder plain = new StringBuilder(clean);
        StringBuilder reverse = plain.reverse();
        return reverse.toString().equals(clean);
    }

    private static boolean isPalindromeUsingStringBuffer(String text) {
        String clean = text.replaceAll("\\s+", "").toLowerCase();
        StringBuffer plain = new StringBuffer(clean);
        StringBuffer reverse = plain.reverse();
        return reverse.toString().equals(clean);
    }

StirngBuffer, StringBuilder에 있는 reverse()함수를 통해 값을 비교해보았습니다.

1.3 Using Stream API

    @Test
    public void streamAPI_test() {
        Assertions.assertTrue(isPalindromeUsingIntStream("racecar"));
    }


    public static boolean isPalindromeUsingIntStream(String text) {
        String temp = text.replaceAll("\\s+", "").toLowerCase();
        return IntStream.range(0, temp.length() / 2)
                .noneMatch(i -> temp.charAt(i) != temp.charAt(temp.length() - i - 1));
    }

문자열의 절반에 대해서 검증을 진행합니다.

1.4 Using Recursion

재귀를 통해서도 가능합니다.

 @Test
public void recursion_test() {
    Assertions.assertTrue(isPalindromeUsingRecursive("racecar"));
}

public static boolean isPalindromeUsingRecursive(String text) {
    String clean = text.replaceAll("\\s+", "").toLowerCase();
    return recursivePalindrome(clean, 0, clean.length() - 1);
}

public static boolean recursivePalindrome(String text, int forward, int backward) {
    if (forward == backward) {
        return true;
    }
    if (text.charAt(forward) != text.charAt(backward)) {
        return false;
    }
    if (forward < backward + 1) {
        recursivePalindrome(text, forward + 1, backward - 1);
    }
    return true;
}

2. Check if a String Can Become a Palindrome by Rearranging

회문의 한가지 특성이 있습니다. 맨 앞글자와 맨 뒤 글자가 같고, 맨 앞의 2번째 글자와 맨 뒤의 2번째 글자와 같고,.. 이런식으로 비교하다보면 한 가지 특성을 찾을 수 있는데 바로 회문은 모든 문자개수가 짝수개이며 최대 한 개의 문자만 홀수개의 문자갯수를 가질 수 있습니다

이러한 특성을 이용해 다음과 같은 코드를 작성할 수 있습니다.

    @Test
    public void anagram_test() {
            Assertions.assertTrue(hasPalindromePermutation("racecar"));
    }

    public static boolean hasPalindromePermutation(String text) {
        long charsWithOddOccurrencesCount = text.chars() // Intstream형태로 변환
                .boxed()// Stream<Intstream>변환
                .collect(Collectors.groupingBy(Function.identity(), Collectors.counting()))// 그룹화작업. key: 문자, value: 갯수
                .values()
                .stream() // 값만가져와서 Long<Stream>으로 재구성
                .filter(count -> count % 2 != 0)// Log<Stream> 값이 1이 아닌것들을 분류
                .count(); // 1이 아닌 것들의 갯수를 셈

        return charsWithOddOccurrencesCount <= 1; // 2를 넘어가면 회문이 아님.
    }

3. 결론

회문 검증에 대한 여러방법들을 학습하였습니다.

---

블로그 주인장 생각

이 문제는 사실상 코딩테스트 외에 크게 쓰일일이 없을 것 같습니다. 성능이 크게 중요하지 않으면 reverse()로 간단하게 구현하지 않을까 합니다.