Python 알고리즘(2)_유효한 팰린드롬, 로그파일의 재정렬

6장 문자열 조작의 내용에 있는 알고리즘을 정리해 보았습니다.

✏️ 유효한 팰린드롬

• 팰린드롬은 앞뒤가 같은 문장이나 단어를 뜻한다.

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

[ 풀이 1 ] 리스트로 변환

def isPallendrome(s):
    strs = []
    for char in s:
        if char.isalnum():   
            strs.append(char.lower())  # 문자를 모두 소문자로 변형
    
    while len(strs)>1:
        if strs.pop(0) != strs.pop():  # 첫번째와 마지막 문자를 비교해서 다르면 false
            return False
    return True

[ 풀이 2 ] 데크 자료형 사용

다음은 데크 자료형을 사용해 최적화 시킨 알고리즘 코드이다.

import collections
from typing import Deque


def isPallendrome(s):
    strs : Deque = collections.deque()
    for char in s:
        if char.isalnum():
            strs.append(char.lower())
    
    while len(strs)>1:
        if strs.popleft() != strs.pop():  # popleft는 O(1)이다
            return False
    return True

이전보다 실행 시간이 훨씬 줄어들었다. 시간복잡도의 차이 : pop(0)은 O(n)이고 popleft()는 O(1)이다.

[ 풀이 3 ] 정규식 슬라이싱 사용

다음으로 정규식을 사용해서 풀어보았다.

def isPallendrome(s):
    s = s.lower()
    s = re.sub('[^a-z0-9]','',s)  # 문자만 꺼내기
    return s == s[::-1]  # 뒤집은 글자와 비교해서 같은지 본다

더 빠른 속도로 끝났다. 슬라이싱을 사용해 바로 자르기!

✏️ 로그파일의 재정렬

정렬의 기준은 다음과 같다

1. 로그의 가장 앞 부분은 식별자다.
2. 문자로 구성된 로그가 숫자 로그보다 앞에 온다.
3. 식별자는 순서에 영향을 끼치지 않지만 문자가 동일할 경우 식별자 순으로 한다.
4. 숫자 로그는 입력 순서대로 한다.

입력

>>> logs = ["dig1 8 1 5 1", "let1 art can","dig2 3 6","let2 own kit dig","let3 art zero"]

출력

>>> ['let1 art can', 'let3 art zero', 'let2 own kit dig', 'dig1 8 1 5 1', 'dig2 3 6']

💡 람다와 연산자 사용하기

로그가 숫자보다 먼저오고, 숫자는 입력 순서대로

풀이방법
1. 먼저 문자와 숫자를 구분해서 받음
2. 구분하는 방법은 isdigit() 함수 사용, 각각의 리스트에 넣는다
3. 그리고 숫자로 변환가능한 로그는 digit에 문자는 letters에 추가된다.
4. 정렬하는 함수를 사용해서 문자를 정렬
5. 두개를 이어서 리턴

def reorder(logs):
    letters, digits = [],[]
    for log in logs:
        if log.split()[1].isdigit():
            digits.append(log)
        else:
            letters.append(log)
    letters.sort(key=lambda x:(x.split()[1:], x.split()[0]))
    return letters + digits