팰린드롬과 문자열 슬라이싱

choonghee-lee·2020년 8월 2일
0

WeCode

목록 보기
15/20

서론

리트코드의 125번 문제 Valid Palindrome을 풀면서 슬라이싱의 위대함에 새삼 놀라게 되었다. 일단 나는 겁나 무식하게 풀었다는 것을 확인하는 순간이기도 했다 ㅋㅋㅋㅋㅋㅋ 😂🤣. 그냥 풀었다는 사실에 만족하고 있었는데 다른 사람들의 답을 보니 아직 가야할 길이 멀다는 것을 느낀다. 그럼 시작해보자!

문제

주어진 문자열이 팰린드롬인지 확인하라. 대소문자를 구분하지 않고, 영문자와 숫자만을 대상으로 한다.

예시 1

Input: "A man, a plan, a canal: Panama"
Output: true

예시 2

Input: "race a car"
Output: false

나의 정답

계속 실행해보면서 테스트케이스에 코드를 맞춰가는 식으로 작성하다보니 조금 복잡해진 것 같다.

def isPalindrome(self, s: str) -> bool:
    s = re.sub(r'[^A-Za-z0-9]+', '', s)
    if not s:
        return True
    s = s.lower()
        
        for i in range(0, (len(s)//2) + 1) :
            bi = -1 + (-1*i)
            try:
                if s[i] != s[bi]:
                    return False
            except IndexError:
                return False
            
        return True

일부러 IndexError 까지 만드는 나의 클래스 ... 😢. 통과는 했지만, 전혀 이렇게 작성하면 안될 것 같다.

문자열 슬라이싱을 이용한 정답

파이썬의 문자열 슬라이싱을 사용하면 코드가 정말 간단해지고, 속도도 정말 빨라진다. 물론 C언어로 작성된 코드에 비할 바는 못된다.

def isPalindrome(self, s: str) -> bool:
    s = s.lower()
    s = re.sub('[^A-Za-z0-9]', '', s)
   	return s == s[::-1]

와우.. 단 세줄에 끝나버렸다 🙀! 이렇게 된 이상 문자열 슬라이싱에 대해 공부를 하지 않고 넘어갈 수가 없게되었다.. ㅋㅋ

문자열 슬라이싱

인덱스를 지정하면 해당 위치의 배열 포인터를 얻게된다. 이를 통해 연결된 객체를 찾아 실제 값을 찾아낸다. 이 과정은 매우 빠르게 진행되기 때문에 문자열을 처리할 때는 슬라이싱을 가장 먼저 생각해보는 것이 좋다.

파이썬 알고리즘 인터뷰라는 책에 알고리즘별 문자열 처리시간 에 대한 테이블이 있어 적어본다.

알고리즘실행 시간슬라이싱을 1로 했을 때의 비율
슬라이싱0.499 마이크로초1
리스트 reverse()2.46 마이크로초5
revsered() + join()2.49 마이크로초6
for 반복5.5 마이크로초12
while 반복9.4 마이크로초21
재귀24.3 마이크로초54

s[:]는 사본을 리턴한다. 이 방식은 문자열이나 리스트를 복사하는 파이썬다운 방식(Pythonic way) 이다. 그리고 s[::-1]은 문자열이나 리스트의 아이템을 뒤집는다. 이 정도를 기억하고 있으면 문자열 처리에 도움이 많이 될 것 같다!

결론

팰린드롬 문제에서 Deque로 푸는 방식도 있었지만 문자열 슬라이싱이 가장 빠른 속도를 자랑했다. Deque는 몰라서 그랬다 치지만 슬라이싱은 알면서도 생각해내지 못한 것이 개인적으로 아쉽다. 좀 더 침착하게 문제를 대하는 자세가 필요하고, 여러가지 입력에 대해 고민해 봐야겠다 😁!

profile
뭐든지 열심히하는 타입 😎

0개의 댓글