코딩 테스트) 문자열 조작

 

유효한 팰린드롬

 

팰린드롬이란? 

 회문 또는 팰린드롬은 거꾸로 읽어도 제대로 읽는 것과 같은 문장이나 낱말, 숫자, 문자열 등을 말한다. 보통 낱말 사이에 있는 띄어쓰기나 문장 부호는 무시한다.

 

 

1.  리스트 변환을 통한 풀이

• .isalnum() : 영문자, 숫자 여부를 판별하는 함수
• .lower() : 소문자로 모두 전환
• .pop(0) : 리스트의 첫 번째 값을 출력하고 제거함
• .pop() : 리스트의 마지막 값을 출력하고 제거함

""" 리스트 활용 함수 """
class Solution:
    def isPalindrome(self, s: str) -> bool:
        str_list = []
        for char in s:
            if char.isalnum():
                str_list.append(char.lower())
        while len(str_list) > 1:
            if str_list.pop(0) != str_list.pop():
                return False
        return True
        
""" 입력 문자 """
s1 = "A man, a plan, a canal: Panama"
s2 = "race a car"
s3 = " "

""" 코드 실행 """
code = Solution() # 클래스 객체 가져오기
start = time.time()
print(start)
code.isPalindrome(s1)

 

 

2. 데크를 사용한 풀이

 

1. 데크(Deque)란?

• Deque라는 것은 파이썬의 list와 같이 요소들을 한 곳에 담아두는 배열
• 파이썬에서 큐 queue는 First In First Out(FIFO)의 방식으로 작동 
• 덱(데큐)는 큐는 큐이지만 양방향인 queue이다. 양 쪽 방향 모두에서 (앞, 뒤) 요소를 추가/제거할 수 있다.

2. 데크의 사용 이유

• List 보다 deque의 속도가 훨씬 빠르다.
• List는 O(n)의 속도, deque는 O(1)의 속도를 가진다. (빅오 표기법으로 나타낸 것)
• Deque는 스택(stack)으로도, Queue(큐)로도 사용할 수 있다.

 이와 같은 이유로 Deque는 성능이 좋고 편리한 List-Like 메서드라고 할 수 있다.

 

3. 데크에 존재하는 메서드(method)

• deque.append(item): item을 데크의 오른쪽 끝에 삽입한다.
• deque.appendleft(item): item을 데크의 왼쪽 끝에 삽입한다.
• deque.pop(): 데크의 오른쪽 끝 엘리먼트를 가져오는 동시에 데크에서 삭제한다.
• deque.popleft(): 데크의 왼쪽 끝 엘리먼트를 가져오는 동시에 데크에서 삭제한다.
• deque.extend(array): 주어진 배열(array)을 순환하면서 데크의 오른쪽에 추가한다.
• deque.extendleft(array): 주어진 배열(array)을 순환하면서 데크의 왼쪽에 추가한다.
• deque.remove(item): item을 데크에서 찾아 삭제한다.
• deque.rotate(num): 데크를 num만큼 회전한다(양수면 오른쪽, 음수면 왼쪽).

 

"""Deque를 사용한 팰린드롬 문제 풀기"""
import time
import collections

class Solution:
    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
        
""" 입력 문자 """
s1 = "A man, a plan, a canal: Panama"
s2 = "race a car"
s3 = " "

""" 코드 실행 """
code = Solution() # 클래스 객체 가져오기
start = time.time()
print(start)
code.isPalindrome(s1)

 

 데크를 사용할 경우, 리스트를 사용한 경우보다 5배 가까이 더 속도를 높일 수 있다. 위의 경우 예시가 2개 밖에 되지 않아서 차이가 크지 않을 수 있으나 input을 여러 개로 해서 테스트를 해보면 차이가 확연하게 나타난다.

• 리스트의 pop(0) : O(n)
• 데크의 popleft() : O(1)

 위 경우들에 대해서 각각 n번씩 반복 구현한다고 하면 리스트는 O(n^2)이고, 데크는 O(n)이 된다.

 

 

3. 슬라이싱 사용

 

class Solution:
    def isPalindrome(self, s: str) -> bool:
        s = s.lower()
        
        # 정규식으로 불필요한 문자 필터링->문자열 전체에서 한 번에 영숫자만 걸러내도록 함
        s = re.sub('[^a-z0-9]', '', s)
        print(s)
        
        ## [::-1]을 통해 문자열 뒤집기
        return s == s[::-1] # 슬라이싱

s1 = "A man, a plan, a canal: Panama"
s2 = "race a car"
s3 = " "

code = Solution()
start = time.time()
print(start)
code.isPalindrome(s1)

 

 앞선 풀이들은 .isalnum()으로 모든 문자를 하나씩 점검했다. 3번째 풀이에서는 한 번에 영숫자만 걸러내도록 하는 정규식을 사용하여 시간을 더 줄였다. 또한 [::-1]을 통해 리스트를 거꾸로 뒤집어서 기존의 문자열과 같은지 확인하였다. 코드의 길이도 줄어들 뿐더러 내부적으로 C로 빠르게 구현되어 있어 훨씬 더 좋은 속도를 기대할 수 있다.

 

S = 안녕하세요
S[:]	둘 다 생략하면 사본을 리턴
S[-3]	뒤에서 3번째 문자
S[:-3]	뒤에서 3개 글자 앞까지
S[-3:]	뒤에서 3번째 문자에서 마지막까지
S[::1]	1은 기본값으로 통일
S[::-1]	뒤집기
S[::2]	2칸씩 앞으로 이동