LINK : 125. Valid Palindrome

문제 설명

주어진 문자열 s가 회문인지 확인하시오. 단, 영숫자 문자만을 고려하며, 대소문자는 무시합니다. 공백, 기호 등은 무시합니다.

예시:

"A man, a plan, a canal: Panama" → true
"race a car" → false

접근 방식

이 문제는 문자열의 양 끝에서 시작하여 중앙으로 향하면서 문자가 서로 일치하는지 확인하면 해결할 수 있습니다. 하지만 이때 주의할 점은 아래와 같습니다:

영숫자(letter 또는 digit)만 비교
대소문자 구분 없음

따라서 문자열을 처음부터 끝까지 순회하며 다음을 수행합니다:

왼쪽 포인터(left)와 오른쪽 포인터(right)를 사용하여 각 문자를 검사합니다.
두 포인터가 가리키는 문자가 영숫자가 아니라면, 해당 포인터를 건너뜁니다.
두 문자가 모두 영숫자이고 서로 대소문자 구분 없이 같다면 다음 비교로 넘어갑니다.
하나라도 다르다면 회문이 아니므로 false를 반환합니다.

구현 코드 (Kotlin)

1차 시도

// 1차 시도
class Solution {
    fun isPalindrome(s: String): Boolean {
        val tmp = s.lowercase().replace("[^a-z0-9]".toRegex(), "")

        for (i in 0 until tmp.length / 2) {
            if (tmp[i] != tmp[tmp.length - i - 1]) return false
        }

        return true
    }
}

정규식을 사용한 풀이 방법 입니다. 해당 수준으로도 문제를 해결할 수 있어서 간단했던 것 같습니다.

2차 시도

class Solution {
    fun isPalindrome(s: String): Boolean {
        val queue = ArrayDeque<Char>()
        for (c in s) {
            if (c.isDigit() || c.isLetter()) queue.add(c.uppercaseChar())
        }

        for (i in 0 until queue.size / 2) {
            val first = queue.removeFirst()
            val last = queue.removeLast()

            if (first != last) return false
        }
        return true
    }
}

2차에는 deque를 사용한 방법을 사용했습니다. 그래서 앞뒤로 하나씩 빼서 확인하는 방식입니다. 다만 이것도 공간복잡도를 많이 잡아먹는 문제가 있습니다.

3차 시도

class Solution {
    fun isPalindrome(s: String): Boolean {
        var left = 0
        var right = s.length - 1

        while (left < right) {
            while (left < right && !s[left].isDigit() && !s[left].isLetter()) {
                left++
            }

            while (left < right && !s[right].isDigit() && !s[right].isLetter()) {
                right--
            }

            if (left == right) break
            if (s[left].lowercaseChar() != s[right].lowercaseChar()) {
                return false
            } else {
                left++
                right--
            }
        }

        return true
    }
}

로직은 복잡하지만 공간복잡도까지 고려한 풀이 방법입니다. 다만 성능은 개선되었지만 가독성이 많이 안좋아진 것 같아서 조금 맘에 들지는 않듭니다.

핵심 포인트

투 포인터(Two Pointer) 방식을 사용하여 시간복잡도는 O(n)입니다.
Kotlin의 isLetterOrDigit(), lowercaseChar()를 이용하여 간결하게 문자를 정규화할 수 있습니다.
left < right 조건을 통해 불필요한 비교를 방지하고 조기 종료도 가능합니다.

결론

회문 문제는 문자열 처리에서 자주 나오는 기초 알고리즘 문제입니다. 이 문제에서 중요한 점은 입력 전처리, 즉 불필요한 문자의 제거와 대소문자 처리입니다. 이 과정만 잘 이해하고 나면 투 포인터 방식으로 쉽게 해결할 수 있습니다.

느낀점

단순한 방식으로 문제를 푸는 것이라면 정규식을 이용해서 푸는 것이 더 빨랐습니다. 난이도는 쉬웠지만 성능을 요구하는 문제라면 고민해야할 부분이나 알아야할 수 있는 부분이 많은 문제였다고 느껴집니다.

[LeetCode] 125. Valid Palindrome

Table of contents