“파이썬 알고리즘 인터뷰” + https://leetcode.com/problems/valid-palindrome/
주어진 문자열이 팰린드롬(회문)인지 아닌지 판별하는 문제. 오래전 코딩 기초를 배울 때 과제로 했었던 기억이 난다. 문자열 조작을 연습하는 데 좋은 소재이긴 한데 지금까지 내가 겪어온 실무에서 문자열 또는 배열 뒤집기를 한 적이 있던가… 하는 일 자체가 깊이를 필요로 하지 않으니 기회가 없었는지도 모르겠다.
초보적인 방법으로 만든다면 for 반복을 돌려서 하나 씩 체크하겠지만 이 책에서는 파이썬 다운(Pythonic) 방법으로 풀이를 보여주고 있다. 단순히 책에 적힌 풀이를 옮겨 적는 수준에 지나지 않겠지만, 이런 문제들이 있다는 걸 기억하기 위해서 하나 씩 적어보자.
# 1. 리스트의 pop()을 이용하기
def isPalindrom(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파이썬은 참 편하다. 리스트, 딕셔너리 같은 기본 자료형이 매우 쓰기 편하게 되어 있어서 웬만한 처리는 저 둘로 커버 할 수 있다. 하지만 곧 한계에 부딪히게 되는데, 아마 성능 문제 때문에 다른 최적화된 자료형에 손을 대야만 한다.
# 2. deque 사용
def isPalindrome(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그냥 리스트 대신 deque라는 자료형을 사용했다. deque에 대해서는 자세히 알아볼 가치가 있다. 기본 리스트의 pop(0)의 복잡도가 O(n)이므로 n번의 반복을 할 경우 복잡도가 O(n^2)이 되어서 그다지 효율적이지는 않다. 실제로 리트코드에서 돌려보니 실행 시간이 4~500ms 정도였다. 그런데 리스트 대신 deque를 사용하면 40~50ms로 빨라진다. deque의 popleft()의 복잡도는 O(1)이라서 n번 반복 시 O(n)이 됨.
즉, 상황에 맞는 다양한 자료형을 쓸 줄 알아야 한다는 게 포인트로 보인다.
# 3. 슬라이싱
def isPalindrome(s: str) -> bool:
s = s.lower()
s = re.sub("[^0-9a-z]","",s)
return s == s[::-1]이건 슬라이싱을 이용한 것인데, 우선 1과 2의 전처리와 다르게 정규표현식으로 알파벳과 숫자를 제외한 문자는 삭제한 것이 현실적이다. 그리고 s[::-1]으로 s를 반전(reverse)한 게 pythonic한 방법으로 보인다.
단순한 문제지만 아무것도 모른 채 마주하면 난 너무 슬플 것 같다. 졸업하고 난 후 지금까지 난 뭐하고 살아온 걸까. 매일이 고통스러운 나날의 연속이다.