[LeetCode] - 125. Valid Palindrome

LeetCode는 프로그래밍 문제를 풀며 코딩 실력을 향상할 수 있는 온라인 플랫폼입니다. 다양한 알고리즘 및 데이터 구조 문제를 제공하며, 면접 대비에 유용합니다. 해당 문제는, LeetCode Problems에서 볼 수 있는 난이도 '쉬움 (Easy)' 단계인 "Valid Palindrome" 문제입니다.

--> https://leetcode.com/problems/valid-palindrome/description/

 

문제 : 

A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.

Given a string s, return true if it is a palindrome, or false otherwise.

---

Example 1 :

Input : s = "A man, a plan, a canal: Panama"

Output : true

Explanation : "amanaplanacanalpanama" is a palindrome.

 

Example 2 :

Input : s = "race a car"

Output : false

Explanation : "raceacar" is not a palindrome.

 

Example 3 :

Input : s = " "

Output : true

Explanation : s is an empty string "" after removing non-alphanumeric characters.

Since an empty string reads the same forward and backward, it is a palindrome.

 

Constraints :

• 1 <= s.length <= 2 * 10^5
• s consists only of printable ASCII characters.

---

이 문제는 주어진 문자열에서 대문자를 소문자로 변환하고, 모든 영숫자가 아닌 문자를 제거한 후, 앞뒤로 같은지 확인하여 회문인지 판단합니다. 제 다른 게시물 중에 Palindrome 문제 하나 더 있으니 Parlindrome에 관심 있으시면 한 번 보시기 바라겠습니다. --> https://jayj-blog.tistory.com/6

[LeetCode] - 9. Palindrome Number

 

이번 문제에서의 제 코드는 상당히 비효율적인 결과가 나왔기에, 솔루션 중에서 가장 효율적인 답안도 함께 인용해 왔으니, 일단 제 코드부터 보시겠습니다 :

 

1. 재이의 코드 :

class Solution {
    public boolean isPalindrome(String s) {
        String s2 = "";
        for (int i = 0; i < s.length(); i++) {
            if (Character.isLetterOrDigit(s.charAt(i))) {
                s2 += s.charAt(i);
            }
        }
        int j = 0;
        int i = s2.length() - 1;
        while (i > j) {
            if (Character.toLowerCase(s2.charAt(i)) != Character.toLowerCase(s2.charAt(j))) {
                return false;
            }
            i--;
            j++;
        }
        return true;
    }
}

 

 

1. 알파벳과 숫자만 남기기:
   • s2는 알파벳과 숫자만 포함하는 새로운 문자열입니다.
   • Character.isLetterOrDigit(s.charAt(i)): 현재 문자가 알파벳이거나 숫자인지 확인합니다.
   • 알파벳이나 숫자인 경우, s2에 추가합니다.
2. 회문 검사:
   • i는 문자열의 끝에서 시작하고, j는 문자열의 처음에서 시작합니다.
   • Character.toLowerCase(s2.charAt(i)) != Character.toLowerCase(s2.charAt(j)): 대소문자를 무시하고 두 문자를 비교합니다.
   • 두 문자가 같지 않으면 false를 반환합니다.
   • 모든 문자가 같으면 true를 반환합니다.

시간 복잡도가 O(n^2)로 아주 베스트는 아니지요...

 

제가 궁금해서 제 코드를 ChatGPT 4o 한테 무엇을 개선하면 좋을 지 물어봐봤는데요, 답변이 이랬습니다 : 

class Solution {
    public boolean isPalindrome(String s) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            if (Character.isLetterOrDigit(s.charAt(i))) {
                sb.append(s.charAt(i));
            }
        }
        
        int j = 0;
        int i = sb.length() - 1;
        while (i > j) {
            if (Character.toLowerCase(sb.charAt(i)) != Character.toLowerCase(sb.charAt(j))) {
                return false;
            }
            i--;
            j++;
        }
        return true;
    }
}

 

개선점 : 

 

• String s2 = "";에서 문자열을 계속해서 더하는 것은 비효율적입니다. 대신 StringBuilder를 사용하는 것이 성능을 향상할 수 있습니다.
• 또한, 한 번의 순회를 통해 문자열을 생성하고 회문을 검사할 수 있습니다.

이는 시간 복잡도가 O(n)입니다. 역시...

 

---

2. 다른 유저의 코드 : 

 

class Solution {
    public boolean isPalindrome(String s) {
        int i = 0;
        int j = s.length() - 1;
        while (i < j) {
            while (i < j && !Character.isLetterOrDigit(s.charAt(i))) {
                i++;
            }
            while (i < j && !Character.isLetterOrDigit(s.charAt(j))) {
                j--;
            }
            if (Character.toLowerCase(s.charAt(i)) != Character.toLowerCase(s.charAt(j))) {
                return false;
            }
            i++;
            j--;

        }
        return true;

    }
}
// Kanishk-Chaudhary 유저의 코드

 

제가 이 코드를 좀 연구를 해봤습니다 : 

1. 포인터 초기화 :
   • i는 문자열의 시작을 가리키는 포인터입니다.
   • j는 문자열의 끝을 가리키는 포인터입니다. 여기까지는 뭐 제 코드랑 비슷합니다. Two Pointers 방식을 쓰려고 했으니까요.
2. 앞뒤 비교 반복문 :
   • 내부 반복문 (앞쪽 포인터 이동) :i 포인터가 가리키는 문자가 알파벳이나 숫자가 아니면 i를 오른쪽으로 이동합니다.
   • 내부 반복문 (뒤쪽 포인터 이동) :j 포인터가 가리키는 문자가 알파벳이나 숫자가 아니면 j를 왼쪽으로 이동합니다.
   • 문자 비교 : i와 j 포인터가 가리키는 문자를 대소문자를 무시하고 비교합니다. 문자가 다르면 회문이 아니므로 false를 반환합니다.
   • 포인터 이동 : 다음 문자를 비교하기 위해 포인터를 각각 이동합니다. 
3. 모든 문자가 같다면 회문 : 문자열을 끝까지 비교했을 때 모든 문자가 같다면 회문이므로 true를 반환합니다.

이 코드의 시간 복잡도는 O(n)입니다. 여기서 n은 문자열 s의 길이입니다.

• 문자열을 처음부터 끝까지 한 번 순회하며, 각 문자를 알파벳과 숫자인지 검사하고 비교합니다.
• 내부의 두 반복문은 각각 문자를 검사하고 건너뛰는 작업을 수행하며, 최종적으로 문자열의 길이에 비례하여 실행됩니다.

확실히 이분의 코드가 더 가독성이 높고, 더 심플하고 어떻게 코드를 짠건지 확 이해가 빠릅니다. 더 효율적이기도 하고, 저도 이 글을 쓰면서 다시 한번 제 코드를 리뷰할 수 있었고, 다른 이들의 코드를 보며 한 수 배워가는 맛이 있어서 너무 재밌고 유익했습니다. 여러분들도 재미로 한 번 해보시는 것 추천드리겠습니다!

---

내 코드, GPT가 쓴 개선된 코드, 다른 유저 코드들의 Runtime 결과