[Leetcode 아주 상세한 문제풀이] 125. Valid Palindrome - 코드 line 별 설명

Leetcode 문제

이번에 풀어볼 문제는 리트코드 125번 문제 Valid Palindrome 이다.

우선 문제를 살펴보자.

 

리트코드 125번 문제 Valid Palindrome 링크

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

Valid Palindrome - LeetCode

 

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 * 105
s consists only of printable ASCII characters.

 

 

문제 설명

문제에 대해 간략히 살펴보자. 우선 용어에 대해 정확히 이해를 해야 할 것 같다. Palindrome이란 쉽게 말해서 앞으로 읽어도 뒤로 읽어도 똑같은 단어나 문장을 말한다. 대표적으로 이상한 변호사 '우영우'가 그 예라고 할 수 있겠다. 앞으로 읽어도 뒤로 읽어도 '우영우'다.

문제에서 요구하는 바는 입력된 문자열 s에 대하여 그것이 palindrome인지 아닌지 판단하라는 것이다. 단, 문자열 s는 띄어쓰기를 포함한 대문자/소문자로 이루어져 있다. 따라서 비교는 모든 대문자를 소문자로 바꾸고 띄어쓰기를 제거한 다음 비교를 해야 한다. 문제 예시 1번에서 보는 것처럼 하나의 문장이 대문자, 소문자, 띄어쓰기를 포함하고 있다. 이 경우 대문자를 소문자로 바꾸고 띄어쓰기를 제거한 다음 앞으로 읽을때와 뒤로 읽을 때를 비교해보면 동일하다. 따라서 이 경우는 palindrome이라고 할 수 있겠다. 문제를 이해하기 어렵지 않으므로 곧바로 문제를 풀어보도록 하자.

 

 

문제 접근법

이 문제에 접근하는 방법은 문제에서 요구하는 바 그대로 하는 것이다.

우선 주어진 문자열이 알파벳으로 이루어져 있는지 확인한다.

그리고 주어진 문자열을 모두 소문자로 바꾸어준다.

그 후 소문자로 바뀐 문자열들을 하나씩 불러와 서로 연결시켜 준다.

마지막으로 서로 연결된 문자열을 앞으로 뒤로 읽어 서로 같은지 비교해주면 된다.

이 문제를 해결하기 위하여 몇 가지 파이썬 내장 함수를 알 필요가 있다.

 

1) isalnum(): 주어진 문자열이 alphanumeric 한지 알아보는 함수다. 즉, 그 문자열이 알파벳 (A-Z)과 숫자 (0-9)으로 이루어져 있는지 체크해주는 함수다. 우리는 알파벳만을 처리하기 위해 이 함수를 이용하여 주어진 문자가 알파벳인지 아닌지 확인할 것이다.

 

2) lower(): 주어진 문자열을 소문자로 바꿔주는 함수다. 예를 들어 주어진 문자열이 s라고 했을 때 s.lower()로 표현함으로써 대문자를 소문자로 바꿀 수 있다. 소문자가 입력될 경우 소문자로 출력된다.

 

3) join(): 주어진 문자열 혹은 숫자를 서로 연결시켜주는 함수다. 여기서 join() 함수 앞에 ''로 표시된 이유는 문자열들을 띄어쓰기 없이 붙여주기 위함이다. 만약 ' '로 한 칸을 띄어 써준다면 문자열들 사이에 공백이 생긴 상태로 연결된다.

이 문제를 해결하기 위한 파이썬 내장 함수에 대해 알아봤으므로 코드로 한 번 살펴보자.

 

 

문제 풀이

문자열을 입력받기 위함 함수를 정의해 준다. (line 1)

앞서 설명한대로 i) 우선 알파벳인지 확인하고, ii) 소문자로 바꾼 후, iii) 서로 연결을 시켜준다. (line 3)

이때 for loop를 이용하여 주어진 문자열의 문자를 하나씩 탐색한다.

문제 접근법에서 설명했듯 문자열 사이에 공백을 없애기 위해 ''.join()으로 표현한다.

이 과정을 마치고 나면 cleaned이라는 변수에 소문자로 이루어진 공백없는 문자열이 저장된다.

문제에서 요구하는 바는 주어진 문자열이 palindrome인지 아닌지 판단하는 것이다.

따라서 cleaned 변수를 앞에서 읽은 것과 (= cleaned) 뒤로 읽은 것 (cleaned[::-1])을 비교한다.

만약 이 둘이 같다면 palindrome이므로 True가 출력되고 같지 않다면 False가 출력되며 종료된다. (line 6)

 

 

문제 풀이 코드

def isPalindrome(s):
    # Convert to lowercase and filter out non-alphanumeric characters
    cleaned = ''.join(ch for ch in s.lower() if ch.isalnum())
    
    # Check if cleaned string is the same as its reverse
    return cleaned == cleaned[::-1]
 
# Test cases
s1 = "A man, a plan, a canal: Panama"
print(isPalindrome(s1))  # Output: true
 
s2 = "race a car"
print(isPalindrome(s2))  # Output: false
 
s3 = " "
print(isPalindrome(s3))  # Output: true
 

 

 

관련 문제

리트코드 3번 Longest substring without repeating characters 문제풀이

리트코드 5번 Longest palindromic substring 문제풀이

리트코드 20번 Valid parenthesis 문제풀이

리트코드 49번 Group anagram 문제풀이

리트코드 76번 Minimum window substring 문제풀이

리트코드 242번 Valid anagram 문제풀이

리트코드 424번 Longest repeating character replacement문제풀이

리트코드 647번 Palindromic substrings문제풀이

 

125. Valid Palindrome