Week 1-2. [Two Pointers] 125. Valid Palindrome (Java)

문제 해결 과정

✍️ 나만의 방식으로 문제 정리하기 (=체계화)

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

Valid Palindrome - LeetCode

주어진 문자열의 모든 대문자는 소문자로 변환하고 특수문자는 제거했을 때, palindrome인지 판별하라.

• 입력
  • s | string := palindrome인지 판별할 문자열, | s | ∈ [1, 2^10^5]
• 출력
  • isPalindrome | boolean := palindrome인지 여부
• 조건
  • s는 ASCII 문자로 출력할 수 있는 문자만 포함한다.

 

🔎 어떤 식으로 접근했는가?

우선 palindrome을 판단하기 전에 모두 소문자로 변경하고, 특수문자를 제거해야 한다. 특수문자는 정규식을 이용해 제거하자.

양 끝에 lp와 rp를 두고, lp++와 rp--로 점차 거리를 좁혀가며 s[lp]와 s[rp]가 서로 달라지는 순간에 false를 반환한다.

 

🙈 알고리즘 선택: 입력의 크기를 바탕으로

s의 최대 길이가 20,000이므로 O(N)까지 감당할 수 있다. 따라서 단일 for문으로 구현하자.

 

📝 의사 코드

lp와 rp를 이용해 양쪽에서 순회하므로 문자열 길이의 절반까지만 순회하면 된다. 마지막에는 중간 지점에서 종료될 것이다. 

s에 포함된 대문자를 소문자로 변경한다.
s에 포함된 특수문자를 제거한다.

lp = 0
rp = 문자열 맨 끝

for (0부터, 절반까지, 1씩 증가) {
	if (s[lp]와 s[rp]가 다르면) {
    	false 반환
    }
}
반복문을 무사히 통과했으면 true 반환

 

🎯 구현 코드

class Solution {
    public boolean isPalindrome(String s) {
        s = s.toLowerCase();
        s = s.replaceAll("[^ㄱ-ㅎㅏ-ㅣ가-힣a-zA-Z0-9]", "");

        int lp = 0;
        int rp = s.length() - 1;

        for (int i=0; i<s.length()/2; i++) {
            if (s.charAt(lp) != s.charAt(rp)){
                return false;
            }
            lp++;
            rp--;
        }
        return true;
    }
}

 

내 코드를 탐구해보기

⏱ 성능 측정 (시간복잡도/공간복잡도)

단일 for문을 사용하여 시간 복잡도는 O(N)이다.

 

✍️ 성능 회고

N은 최대 20,000이므로 감당할 수 있는 범위이다.

 

보통 1초 제한이라고 할 때, O(N)은 약 1억까지 O(N^2)은 약 1만까지 감당할 수 있다.

따라서 해당 문제를 2중 for문으로 구현한다면 터지게 될 것이다.

 

💡 무엇을/어떻게 개선할 수 있을까?

정규식을 확실히 알지 못하면 구현할 수 없는 코드라는 것이 아쉽다.

가능하면 정규식을 사용하지 않고 구현하면 좋을 것 같다. 하지만 방법이 잘 떠오르지 않는다.

 

다른 사람의 코드를 탐구해보기

🎯 구현 코드

아래 코드에서는 정규식을 사용하는 대신 특수문자라면 건너뛴다.

class Solution {
    public boolean isPalindrome(String s) {
        int lp = 0;
        int rp = s.length() - 1;

        while (lp <= rp) {
            if (!Character.isLetterOrDigit(s.charAt(lp))) {
                lp++; // ✅ lp가 가리키는 문자가 특수문자라면 건너뛴다.
            } else if (!Character.isLetterOrDigit(s.charAt(rp))) {
                rp--; // ✅ rp가 가리키는 문자가 특수문자라면 건너뛴다.
            } else {
                if (Character.toLowerCase(s.charAt(lp)) != Character.toLowerCase(s.charAt(rp))) {
                    return false; // 서로 다른게 나오면 바로 false 리턴
                }
                lp++;
                rp--;
            }
        }
        return true;
    }
}

 

⏱ 성능 측정 (시간복잡도/공간복잡도)

while문을 사용하여 시간 복잡도는 O(N)이다.

추가 데이터 구조를 사용하지 않았기 때문에 공간 복잡도는 O(1)이다.

 

느낀 점

정규식을 제외하고는 어렵지 않은 문제였다.

정규식을 오랜만에 보니 막막했다. 결국 이번에는 검색을 했지만 다시 익혀두어야겠다. 

정규식을 사용하지 않고 isLetterOrDigit() 메서드를 사용하는 방법도 알아두어야겠다.