[1주차] 125. Valid Palindrome

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

Valid Palindrome - LeetCode

---

이 문제부터는 Kotlin이 아닌 Java 로 풀기로 하였다. Kotlin을 지원안하는 코딩테스트를 벌써 두 번이나 마주쳤기 때문.

코틀린 신봉자로써 너무 슬프다.

 

📝 문제

모든 대문자를 소문자로 변환하고, 영숫자가 아닌 문자를 모두 제거한 뒤 회문이 되면 true. 회문이 아니면 false를 리턴하라

 

 

🎈 풀이

투 포인터를 이용하여 해결하였다.

 

시간복잡도: O(n)

공간복잡도: O(1)

public boolean isPalindrome(String s) {
    if (s.length() == 1) return true;

    int left = 0;
    int right = s.length() - 1;
    while (left < right) {
        char c1 = s.charAt(left);
        char c2 = s.charAt(right);
        while (!(Character.isLetter(c1) || (c1 >= '0' && c1 <= '9'))) {
            // c1이 영문자나 숫자가 아니라면
            if (++left > right) break;
            c1 = s.charAt(left);
        }

        while (!(Character.isLetter(c2) || (c2 >= '0' && c2 <= '9'))) {
            // c2가 영문자나 숫자가 아니라면
            if (left > --right) break;
            c2 = s.charAt(right);
        }

        if (c1 >= 'A' && c1 <= 'Z') c1 = (char)(c1 + 32);
        if (c2 >= 'A' && c2 <= 'Z') c2 = (char)(c2 + 32);
        if (c1 != c2) return false;
        left++;
        right--;
    }

    return true;
}

• left는 문자열 시작점을 가리키며, right는 문자열 끝 점을 가리킨다.
• left는 증가하고, right는 감소하면서 문자를 비교하여 서로 다르면 false를 바로 리턴하고, 루프를 다 마치면 true 이다.
• 9, 15행: 만약 현재 포인터가 가리키는 문자가 영숫자가 아니라면 포인터를 계속 민다.
• 21,22행: 만약 현재 포인터가 가리키는 문자가 대문자이면 소문자로 변환한다.
•  

 

만약 메모리를 사용한다면 코드를 조금 더 간결하게 작성할 수 있다.

 

시간복잡도: O(n)

공간복잡도: O(n)

public boolean isPalindrome(String s) {
    StringBuilder sb = new StringBuilder();
    for (int i=0; i<s.length(); i++) {
        char c = s.charAt(i);
        if ((c >= 'a' && c <= 'z') || (c >= '0' && c <= '9')) sb.append(c);
        if (c >= 'A' && c <= 'Z') sb.append((char)(c + 32));
    }
    int left = 0;
    int right = sb.length() - 1;
    while (left < right) {
        if (sb.charAt(left++) != sb.charAt(right--)) return false;
    }

    return true;
}

• 포인터를 이동시키는 루프를 들어가기 전에 영소문자와 숫자만 삽입하여 String을 만든다.
• 그 이후 로직은 첫 솔루션과 같다.

 

가독성도 물론 중요하지만 공간복잡도 O(1) 에 해결할 수 있는 문제를 O(n)으로 내린건 좀 불편하긴 하다.

하지만 코딩테스트는 시간싸움이기 때문에 쉬운 알고리즘으로 일단 통과시켜놓고 다른 문제를 푸는 방식으로 해야 한다.

 

 

📈 타 솔루션 참고

시간복잡도: O(n)

공간복잡도: O(1)

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;
}

나는 Character.isLetter() 만을 사용했는데, 영숫자를 한번에 판별하는 Character.isLetterOrDigit() 가 있었다.

IDE를 사용하였으면 발견했을텐데 안타깝게도 거의 모든 코딩테스트는 ChatGPT가 나온 이후 IDE 사용과, 인터넷 검색을 허용하지 않기 때문에 이런 유틸성 라이브러리를 암기해야 겠다.

 

또한 내 코드는 left 혹은 right를 한번에 미는 시도를 하면서 불필요하게 while문을 사용하였기 때문에 가독성이 더 떨어져버렸다.

 

그리고 대문자일 경우 c1, c2에 대문자 변환식을 추가하는 조건식을 넣었는데, Character.toLowerCase() 를 사용하면 해당 조건식을 안 써도 된다. toLowerCase() 에 소문자를 넣어도 그대로 소문자를 리턴해주기 때문이다.