[Two Pointers + 테스트 코드 + 리팩토링] Leetcode 125. Valid Palindrome

https://leetcode.com/problems/valid-palindrome/?envType=study-plan-v2&envId=top-interview-150

Valid Palindrome - LeetCode

https://github.com/fineman999/algorithm_java/issues/2

125. Valid Palindrome · Issue #2 · fineman999/algorithm_java

1. 들어가기 전

8월 26일 주말이 되었다. 이번 주말에는 원티드에서 제공해준 문제들을 풀려고 한다. 

1주차 원티드 제공 문제

알고리즘을 풀면서 이전에 배웠던 지식을 추가적으로 녹여내면 좋을 것 같다. 

2. 알고리즘 내용

• 모든 대문자를 소문자로 변환하고 모든 영숫자가 아닌 문자를 제거한 후 앞뒤가 동일한 문자일 경우 true를 리턴한다.
• 영숫자 문자에는 문자와 숫자가 포함된다.
• s가 메소드로 주어지고, 팰린드롬일 경우 true, 아니면 false를 반환한다.

3. 테스트 코드 작성

class SolutionTest {
    static Stream<Arguments> generateTrue() {
        return Stream.of(
                Arguments.of("A man, a plan, a canal: Panama"),
                Arguments.of(" ")
        );
    }
    @ParameterizedTest
    @MethodSource("generateTrue")
    @DisplayName("isPalindrome 메서드는 문자열을 받아 Palindrome 일 경우에는 true 를 반환한다.")
    void example(String value) {
        boolean palindrome = Solution.isPalindrome(value);
        assertThat(palindrome).isTrue();
    }

    @Test
    @DisplayName("isPalindrome 메서드는 문자열을 받아 Palindrome 이 아닐 경우에는 false 를 반환한다.")
    void exampleFalse() {
        String s = "race a car";
        boolean palindrome = Solution.isPalindrome(s);
        assertThat(palindrome).isFalse();
    }
}

주어진 예제로 테스트 코드를 작성해보았다.

테스트 코드 실행

아직 프로덕션 코드가 작성되어 있지 않아서 test가 fail되는 부분들이 있다. 이제 작성해보자.

4. 코드 작성

package org.leetcode.validpalindrome;

import java.util.StringJoiner;

public class Solution {
    private final StringBuilder sb = new StringBuilder();


    public boolean isPalindrome(String s) {
        String convertedString = convert(s);
        int length = convertedString.length();
        int left = 0;
        int right = length - 1;

        while (left < right) {
            if (convertedString.charAt(left++) != convertedString.charAt(right--)) {
                return false;
            }
        }
        return true;
    }

    private String convert(String s) {
        for (char c : s.toCharArray()) {
            if (Character.isLetterOrDigit(c)) {
                sb.append(Character.toLowerCase(c));
            }
        }
        return sb.toString();
    }
}

convert(String s) 메서드를 통해 영숫자일 경우에만 StringBuilder에 저장한 후 string으로 반환하게 된다. 그런 다음 while 문을 통해 앞뒤가 동일하지 않을 경우 false를 반환하게 된다. while문을 벗어나게 되면 true가 반환된다.

4.1 StringBuilder

StringBuilder는 문자열을 가변적으로 조작하기 위한 클래스이다. 다만 StringBuilder는 StringBuffer와는 다르게 내부적으로 동기화 메커니즘이 없다. 그러므로 멀티 스레드 환경에서는 적합하지 않지만 StringBuffer보다 빠른 성능을 제공한다고 알려져 있다. 추가적으로 자바 8부터 도입된 StringJoiner가 있다. StringJoiner 같은 경우 StringBuilder와 동일하게 스레드 안전하지 않지만 요소 사이에 구분자를 지정하여 문자열을 결합할 수 있다.

4.2 결과

단위 테스트 결과

LeetCode 테스트 결과

5. 성능 개선

class Solution {
    public boolean isPalindrome(String s) {
        if (s.isEmpty()) {
        	return true;
        }
        int start = 0;
        int last = s.length() - 1;
        while(start <= last) {
        	char currFirst = s.charAt(start);
        	char currLast = s.charAt(last);
        	if (!Character.isLetterOrDigit(currFirst )) {
        		start++;
        	} else if(!Character.isLetterOrDigit(currLast)) {
        		last--;
        	} else {
        		if (Character.toLowerCase(currFirst) != Character.toLowerCase(currLast)) {
        			return false;
        		}
        		start++;
        		last--;
        	}
        }
        return true;
    }
}

LeetCode 테스트 결과

StirngBuilder를 사용하지 않고 바로 while문에 접근하여 왼쪽과 오른쪽이 모두 영숫자일 경우에만 체킹하는 식으로 하니 2배 빠른 속도가 된 걸 확인했다. 성능을 중요시 한다면 StringBuilder 같은 가변적으로 조작하는 클래스를 덜 이용하는 것이 좋겠다.

6. 리팩토링

위의 코드는 이펙티브 자바에서 말하는 유틸리티 클래스와 동일해 보인다. 아이템 4.인스턴스화를 막으려거든 private 생성자를 사용하라에서 말한 공식을 적용해보자.

public final class Solution {

    /**
     * 이 클래스는 인스턴스를 만들 수 없습니다.
     */
    private Solution() {
        throw new AssertionError();
    }

    public static boolean isPalindrome(String s) {
        checkNull(s);

        if (s.isEmpty()) {
            return true;
        }
        int start = 0;
        int last = s.length() - 1;

        while(start <= last) {
            char currFirst = s.charAt(start);
            char currLast = s.charAt(last);
            if (!Character.isLetterOrDigit(currFirst)) {
                start++;
                continue;
            }
            if(!Character.isLetterOrDigit(currLast)) {
                last--;
                continue;
            }

            if (Character.toLowerCase(currFirst) != Character.toLowerCase(currLast)) {
                return false;
            }
            start++;
            last--;
        }
        return true;
    }

    private static void checkNull(String s) {
        if (s == null) {
            throw new IllegalArgumentException("s cannot be null");
        }
    }
}

• 유틸리티 클래스는 정적 메서드만 담고 있으므로 인스턴스로 만들어 쓰려고 설계한 클래스가 아니다. 그러므로 누군가가 인스턴스를 만들지 못하게 방지하는 것이 좋다.
• 생성자에 주석으로 인스턴화 불가한 이유를 설명하는 것이 좋다. 
• null을 파라미터 값으로 받을 시 에러가 발생하는 메서드를 추가하였다.

단위 테스트 결과