[Java] 125. Valid Palindrome

문제 파악

모든 대문자를 소문자로 변환 후, 숫자와 알파벳이 아닌 문자를 제거한 문자가 뒤로 읽었을때와 앞으로 읽었을때가 같으면 palindrome 이라고 한다. 

 

palindrome 이 맞으면 true를, 아니면 false를 반환하라

 

---

풀이

 

1️⃣ StringBuilder 사용 풀이

 

💡 떠오른 Idea

먼저, 공백과 문자 혹은 숫자가 아닌 것들을 제거해서 붙이는 작업이 필요하다.

그리고, 역순으로 나열한 문자와 동일한지 확인해서 palindrome 인지 확인하면 될 것이다.

 

class Solution {
    public boolean isPalindrome(String s) {
        StringBuilder sb = new StringBuilder();
        char[] arr = s.toLowerCase().toCharArray();

        for (char ch : arr) {
            if (isAlpha(ch) || isNum(ch)) {
                sb.append(ch);
            }
        }

        return sb.toString().equals(sb.reverse().toString());
    }

    private boolean isAlpha(char ch) {
        if ('a' <= ch && ch <= 'z') {
            return true;
        } else {
            return false;
        }
    }

    private boolean isNum(char ch) {
        if ('0' <= ch && ch <= '9') {
            return true;
        } else {
            return false;
        }
    }
}

 

알파벳인지 체크하는 메서드는 isAlpha() 그리고 숫자인지 체크하는 메서드는 isNum() 으로 분리하였다.

 

그리고 StringBuilder 를 사용하면 reverse() 라는 메서드로 역순으로 정렬할 수 있어서 편리하게 palindrome 인지 체크할 수 있었다.

 

결과

 

 

 

2️⃣ 투포인터 방식 풀이

 

아무래도, 투포인터 유형 문제이기 때문에 투포인터로도 풀어보기로 했다.

 

숫자와 알파벳만 남겨두고 palindrome 을 체크하는 과정을 투 포인터 방식으로 확인해보면 된다.

 

public boolean isPalindrome(String s) {
        StringBuilder sb = new StringBuilder();
        char[] arr = s.toLowerCase().toCharArray();

        for (char ch : arr) {
            if (isAlpha(ch) || isNum(ch)) {
                sb.append(ch);
            }
        }

        String[] strs = sb.toString().split("");

        int left = 0, right = strs.length - 1;

        while (left < right) {
            if (!strs[left++].equals(strs[right--])) {
                return false;
            }
        }
        return true;
    }

    private boolean isAlpha(char ch) {
        if ('a' <= ch && ch <= 'z') {
            return true;
        } else {
            return false;
        }
    }

    private boolean isNum(char ch) {
        if ('0' <= ch && ch <= '9') {
            return true;
        } else {
            return false;
        }
    }

 

결과

첫번째 방식보다는 약간 실행시간이 길어졌지만, 통과할 수 있었다.

 

---

📖 회고

투 포인터 방식의 문제를 여러개 풀어보니, 다양한 상황에서 적용할 수 있게 된 것 같다.

 

시간 복잡도를 O(N) 으로 만들 수 있으니, 탐색 범위가 많은 경우에는 잘 떠올려서 적용 시켜 해결해야겠다는 생각이 들었다.