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

입력

"A man, a plan, a canal: Panama"

출력

True

풀이 #1

O(n^2)

"리스트로 변환"

s = "A man, a plan, a canal: Panama"


def isPalindrome(str):
    # 전처리
    strs = []
    for char in s:
        if char.isalnum():
            strs.append(char.lower())

    print(strs)

    # 팰린드롬 여부 판별
    while len(strs) > 1:
        if strs.pop(0) != strs.pop():
            return False

    return True


result = isPalindrome(s)
print(result)

풀이 #2

O(n)

"데크 자료형을 이용한 최적화"

from typing import Collection, Deque

s = "A man, a plan, a canal: Panama"


def isPalindrome(str):
    # 자료형 데크로 선언
    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


result = isPalindrome(s)
print(result)

Deque를 명시적으로 선언하면 좀 더 속도를 높일 수 있다.
collection 모듈의 deque는 스택과 큐의 기능을 모두 가지고 있다.
간단하게 deque의 사용법을 알아보자.

deque 만들기

from collections import deque
dq = deque("python")

#deque(['p', 'y', 't', 'h', 'o', 'n'])

deque - stack (append(), pop())

dq.append('d')
# deque(['p', 'y', 't', 'h', 'o', 'n', 'd'])

dq.pop()
# 'd'
# deque(['p', 'y', 't', 'h', 'o', 'n'])

deque - queue ( appendleft( ), pop( ), append( ), popleft( ) )

dq.appendleft('a')
#deque(['a', 'p', 'y', 't', 'h', 'o', 'n'])

dq.popleft()
#'a'
#deque(['p', 'y', 't', 'h', 'o', 'n'])

ex = list('good')
# ex = ['g', 'o', 'o', 'd']

dq.extend(ex)
# deque(['p', 'y', 't', 'h', 'o', 'n', 'g', 'o', 'o', 'd'])

dq.extendleft(ex)
# deque(['d', 'o', 'o', 'g', 'p', 'y', 't', 'h', 'o', 'n', 'g', 'o', 'o', 'd'])

dq.remove('d')
# deque(['o', 'o', 'g', 'p', 'y', 't', 'h', 'o', 'n', 'g', 'o', 'o', 'd'])

dq.remove('o')
# deque(['o', 'g', 'p', 'y', 't', 'h', 'o', 'n', 'g', 'o', 'o', 'd'])

dq.clear()
# deque([])

dq = deque('apple')
dq.reverse()
# deque(['e', 'l', 'p', 'p', 'a'])

dq.rotate()
# deque(['a', 'e', 'l', 'p', 'p'])

dq.rotate(-1)
# deque(['e', 'l', 'p', 'p', 'a'])

dq.rotate(2)
# deque(['p', 'a', 'e', 'l', 'p'])

풀이 #1의 경우, O(n^2)
풀이 #2의 경우, O(n)

pop(0)이 O(n)인 데
popleft()는 O(1)이기 때문

더 좋은 다른 풀이 방법 (슬라이싱 사용, C구현)

"슬라이싱을 이용한 문제 풀이 코드"

import re

s = "A man, a plan, a canal: Panama"


def isPalindrome(s):
    s = s.lower()
    s = re.sub('[^a-z0-9]', '', s)          # s에서 [^a-z0-9]에 해당하는 부분을 ''로 대체하라는 의미
                                            # [^a-z0-9]: a~z, 0~9의 모든 문자와 숫자를 제외한 나머지를 모두 공백으로 바꾸라는 뜻
    return s == s[::-1]                     # 슬라이싱 s[::-1]의 뜻은 "안녕하세요"를 "요세하녕안"으로 바꾼다는 뜻이다.


result = isPalindrome(s)
print(result)

re.sub를 사용하기 위해서는 먼저 re 모듈을 import 해야 한다.

C는 내가 배울게 아니라서 넘어간다.

풀이 #1은 304밀리초,
풀이 #2는 64밀리초,
슬라이싱은 36밀리초,
C로 구현하면 4밀리초가 걸린다