펠린드롬

앞에서부 읽으나 뒤에서 부터 읽으나 똑같은 글자

한자로 회문( 回文 ) 이라고 한다.

생각

앞에서 읽으나 뒤에서 읽으나 같다 ?

반으로 뚝 잘라서 데칼코마니가 되어야 함

일차적으로 string 을 개별 char 로 구성된 list 로 변환함

반복문을 돌리는데 list 맨앞에서 뽑은 char 와 맨뒤에서 뽑은 char 가 전부 같으면 펠린드롬

하나라도 다르면 아님

# 대만 천연가스버스가 연 천만 대
# 진용진

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

단순히 list 를 pop 해버리면 시간복잡도 관점에서 안좋은 풀이가 된다.

pop() 은 맨뒤에서 나가는거라 O(1) 이지만
pop(0) 은 맨앞에서 나가면 나머지 애들이 한칸씩 땡겨줘야 해서 O(n) 이 된다.

때문에 스택, 큐를 합친 dequeue 를 사용하면 맨앞에서 삭제하는 것도 O(1) 로 만들 수 있어
시간복잡도를 줄일 수 있다.

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
        
      

isalnum

Return True if the string is an alpha-numeric string, False otherwise.

pop

Remove and return item at index (default last).