파이썬을 이용한 알고리즘 공부 내용을 정리합니다.

---

문제

LeetCode-125

주어진 문자열이 팰린드롬인지 확인하라. 단, 문장은 대소문자를 구분하지 않으며 영문자와 숫자로만 구성되어있다.

팰린드롬이란?

'소주 만 병만 주소'와 같이 뒤집어 읽어도 똑같이 읽히는 문장을 말한다.

---

1. 리스트로 변환하여 풀이

def isPalindrome(self, s: str) -> bool:
    strs = [] 				#리스트 선언
    for char in s: 			#s에 문제의 input이 담긴다.
        if char.isalnum():		#isalnum()로 숫자,영문자를 걸러낸다.
            strs.append(char.lower())	#모두 소문자로 변환 후 strs에 넣어준다.

    #팰린드롬 여부를 판별
    while len(strs) > 1:		#strs의 속성이 있는 동안
        if strs.pop(0) != strs.pop():	#양 끝단의 속성이 같은문자인지 비교한다.
            return False	
            
    return True

주요 내용

• isalnum()은 영문자, 숫자여부를 판별하는 함수이다.
• pop()함수를 이용해 맨 뒤의 속성을 리턴받고 리스트에서 뺄 수있다.
• 파이썬의 리스트는 pop()에서 인덱스를 지정 가능하기 때문에 0을 인덱스로 지정하여 맨 앞의 값도 가져올수 있다.

결과

다음과 같이 문제를 해결할 수도 있으나 실행속도가 그리 빠른 해결법은 아니라고 한다. 2번 풀이를 통해 최적화를 진행할 수 있다.

---

2. 데크 자료형을 사용

def isPalindrome(self, s: str) -> bool:

    strs: Deque = 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

주요 내용

• 데크 자료형이기 때문에 popleft() 함수를 이용하여 첫번째 요소를 가져올수 있으며, 각 함수의 시간복잡도에서 차이가 난다.

  pop(n) = O(n)
  popleft() = O(1)

결과

n번 반복하면 1번풀이의 시간복잡도는 O(n^2), 2번풀이는 O(n)으로 차이가 난다. 3번을 통해 좀더 최적화를 진행해보자

---

3. 슬라이싱 사용

def isPalindrome(self, s: str) -> bool:
   s = s.lower()			#input을 소문자로 변경
   s = re.sub('[^a-z0-9]', '', s)	#정규식을 이용해서 문자를 필터링

   return s == s[::-1]			#[::-1]<<(슬라이싱)을 이용하여 문자열을 뒤집고 같은지 비교한다. 

주요 내용

• 정규표현식

  re.sub('패턴', '바꿀문자열', '문자열', 바꿀횟수)

• 슬라이싱 기능

  • '안녕하세요'를 슬라이싱 한 결과
    s[1:4] = 녕하세
    s[1:-2] = 녕하
    s[1:] = 녕하세요
    s[:] = 안녕하세요
    s[1:100] = 녕하세요
    s[-1] = 요
    s[-4] = 녕
    s[:-3] = 안녕
    s[-3:] = 하세요
    s[::1] = 안녕하세요
    s[::-1] = 요세하녕안
    s[::2] = 안하요

결과

파이썬에서 제공하는 슬라이싱 기능을 사용하면 매우 빠르게 조작할 수 있으므로 문자열 조작시에는 우선적으로 사용을 고려한다