리트코드 125. Valid Palindrome JAVA

문제

문제 해석

간단하게 특수문자랑 띄어쓰기 제거하고 로직을 구현하는 것이다.
Alphanumeric characters include letters and numbers. 라는 문구는 결국 알파벳에는 알파벳과 숫자만 포함된다를 의미한다.

문제를 보고 크게 2가지의 방법을 고민했다.

1. 일단 특수문자, 띄어쓰기를 모두 제거한 뒤 for문을 써서 검증하는 방법
2. 한번에 같이 체크하는 방법

1번 방법을 이용할 때는 정규식을 써서 한번에 제거할 것이다.
정규식을 사용하면 속도는 느리지만 간결하고 확실하게 원하는 것들을 제거할 수 있다. 또한 여기저기 많이 사용되기 때문에 어느정도는 익숙해지는 것이 좋다고 판단했다.

2번 방법을 이용할 때는 Character의 메서드를 이용할 생각이다.

1번을 사용하던 2번을 사용하던 한번의 반복에서 2개의 변수를 이용해서 검증을진행하는 Two Pointers를 이용한다.

1번 방법

수도코드

띄어쓰기 특수문자 replace로 제거
while()
    가장 앞과 뒤를 비교
        틀리면 return
    같으면 진행

정규식을 활용해 띄어쓰기, 특수문자를 한번에 제거한 뒤 while을 이용해서 검증한다.

코드

class Solution {
    public boolean isPalindrome(String s) {
        s = s.toLowerCase().replaceAll("[\\s\\W_]","");
        int start = 0;
        int end = s.length()-1;
        while(end > start){
            if(s.charAt(start++) != s.charAt(end--)){
                return false;
            }
        }
        return true;
    }
}

장점

• 코드가 간결하다.
  • if문이 적게 들어갔기 때문에 가독성이 좋다.
    단점
• 속도가 느리다.
  • 정규식의 처리 자체가 리소스가 많이 들기 때문에 속도가 느리다.

실행 시간을 보면 18ms가 걸린다.

2번 방법

수도코드

시작 위치, 끝 위치의 변수 생성

반복 (시작이 < 끝)
    시작 문자 변수
    끝 문자 변수
    if 시작 문자가 지정된 문자 이외의 문자
        시작 변수 증가
    if  끝 문자가 지정된 문자 이외의 문자
        끝 변수 감소
    if 끝 문자의 소문자화 , 시작문자의 소문자화 같으면 false
    아니면 끝 시작 변수 증가

직접 사용했던 수도코드다.

수도코드를 보면 정해진 문자가 아닌 문자일 경우 인덱스의 증감을 시킨 이 후 검증을 진행한다.

코드

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

if문이 많지만 속도는 정말 빠르다.

장점

• 속도 1번 방법의 1/9 정도 걸렸다.
• 메모리 사용량이 1번 방법에 비해 적게 사용되었다.
  단점
• 가독성

회고

정규식을 쓰면 속도는 느리지만 가독성은 좋다.
2번 방식을 이용할 경우 가독성이 좋지 않지만 속도는 빠르다.