리트코드(LeetCode) 125번 Valid Palindrome (유효한 팬린드롬)

---

Palindrome(팰린드롬) 이란 무엇일까? 

팬린드롬이란 앞뒤가 똑같은 단어나 문장으로, 뒤집어도 같은 말이 되는 단어 또는 문장이다

예를 들어 '토마토' 'level' 같은 단어들이 팬린드롬이라 할 수 있다.

 

이 문제는 주어진 문자열이 팰린드롬인지 확인하는 문제이다. 

대소문자는 구분하지 않으며, 영문자와 숫자만을 대상으로 한다.

 

 

 

---

 

 

 

📌 첫번째 풀이 : 리스트로 변환

직접 문자열을 받아 단어가 영문자 또는 숫자인지 확인한다 (특수문자인 것을 거르기 위한 작업)

strs = []
for char in s:
	if char.isalnum(): 
		strs.append(char.lower())

 

 

여기서 isalnum( ) 메소드는 영문자, 숫자 여부를 판별하는 함수로, 이를 이용해 해당하는 문자만을 strs리스트에 추가해준다.

만약 여기에 ' l,e,v,e,l ' 과 같은 문자열이 들어간다면 strs에는 [ 'l', 'e', 'v', 'e', 'l' ] 다음과 같이 담게기 된다.

 

 

이제 팰린드롬 여부를 확인해야 한다.

while len(strs) > 1:
	if strs.pop(0) != strs.pop():
	    return False
return True

 

 

파이썬의 리스트는 pop( ) 함수에서 인덱스를 지정할 수 있기 때문에 인덱스를 0으로 지정해 주어 첫글자와 마지막 글자를 비교해준다.

모두 통과했다면 True를 리턴한다.

 

 

 

전체 코드는 다음과 같다. (리트코드 제출방식)

class Solution:
    def isPalindrome(self, s: str) -> bool:
        strs = []
        for char in s:
            if char.isalnum(): 
                strs.append(char.lower())
		
        # 팬린드롬 여부 판별
        while len(strs) > 1:
            if strs.pop(0) != strs.pop():
                return False
        return True

 

 

 

📌 두번째 풀이 : 데크 자료형을 이용한 최적화

만약 데크를 사용한다면 어떨까? 아마 처리속도가 더 증가하게 될것이다.

그저 리스트를 데크로만 변경해보겠다

 

class Solution:
    def isPalindrome(self, s: str) -> bool:
        strs = collections.deque()
        for char in s:
            if char.isalnum(): 
                strs.append(char.lower())

        while len(strs) > 1:
            if strs.popleft() != strs.pop():
                return False
        return True

 

똑같은 알고리즘이지만

리스트를 데크로 변경시켜주었고 pop(0) -> popleft( ) 로 변경시켜주었다.

 

 

 

 

시간을 확인해본 결과

• 리스트 -> 296ms
• 데크 -> 52ms

로 6배 정도 시간차이가 나는 것을 확인할 수 있었다.