[알고리즘 문제 풀이] 유효한 팰린드롬

sungw00 2022. 8. 12. 14:22

728x90

문제

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

예제1

입력

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

출력

true

예제2

입력

"race a car"

출력

false

풀이1 리스트로 변환하기

이 분제에서는 직접 문자열을 입력받아서 팰린드롬 여부를 확인한다. 문제 설명 중 중요한 부분은 대소문자 여부를 구분하지 않으며 영문자와 숫자만을 대상으로 한다는 제약 조건이 있다. 따라서 이부분에 대한 전처리부터 구현한다.

result = []
for ar in arr:
    if ar.isalnum():
        result.append(ar.lower())

여기서 isalnum( )는 영문자, 숫자 여부를 판별하는 함수로, 이를 이용해 해당하는 문자만 result에 추가한다. 또한 대소문자를 구분하지 않으므로 lower( )로 모두 소문자로 변환한다. 반대로 upper( )로 모두 대문자로 변경해도 상관 없다.

이렇게 하면 입력값이 A man, a plan, a canal: Panama일 때 result 리스트는 다음과 같은 값들이 담기게 된다.

['a', 'm', 'a', 'n', 'a', 'p', 'l', 'a', 'n', 'a', 'c', 'a', 'n', 'a', 'l', 'p', 'a', 'n', 'a', 'm', 'a']

이제 다음과 같이 팰린드롬 여부를 판별해보자.

여기서 중요한 점은 리스트에서 값을 추출할 때 pop( )함수를 이용할 수 있다는 점이다.

pop( ) 함수는 괄호 안에 원하는 인덱스를 넣어 값을 추출할 수 있으며, 해당 요소를 돌려주고 그 요소는 삭제하게 된다.

이 함수를 이용하여 처음 값(0)과 마지막 값( )을 추출하여 같은지 비교하고, 같지 않다면 곧바로 break로 반복문을 탈출하도록 하고,

만약 break를 통한 반복문을 탈출하지 않았다면 True를 리턴하여 팰린드롬 여부가 맞다는 것을 반환하면 된다.

    while len(result) > 1:
        if result.pop(0) != result.pop():
            return False
    # 팰린드롬이 맞다면 True 반환
    return True

전체 코드는 다음과 같다.

# 풀이1. 리스트로 변환
def solution(arr: str) -> bool:
    result = []
    for ar in arr:
        if ar.isalnum():
            result.append(ar.lower())

    print(result)

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

array = input("문자열 입력: ")
print(solution(array))

풀이2 자료형을 데크로 선언해서 속도를 높이기

자료형이 바뀌었다고 실행 속도가 무슨 상관일까라고 생각할 수 있지만, 자료형마다 내부 함수를 구현하는 방법이 다르기 때문에 실행 속도에 당연히 차이가 있을 수 밖에 없다. 실제로 리스트의 pop(0)이 O(n)이지만, 데크의 popleft( )는 O(1)이기 때문에 각각 n번씩 반복하면 리스트는 O(n^2), 데크는 O(n)으로 성능 차이가 크다.

# 풀이2. 데크 자료형을 이용한 최적화
import collections
from typing import Deque

def solution(arr: str) -> bool:
    result = []
    # 자료형 데크로 선언
    result: Deque = collections.deque()
    for ar in arr:
        if ar.isalnum():
            result.append(ar.lower())

    while len(result) > 1:
        if result.popleft() != result.pop():
            return False
    return True


array = input("문자열 입력: ")
print(solution(array))

풀이3 파이썬의 최적화된 내부 기능인 슬라이싱을 이용한 풀이

import re

def solution(arr: str) -> bool:
    arr = arr.lower()
    # 정규식으로 불필요한 문자 필터링
    arr = re.sub('[^a-z0-9]', '', arr) # arr에서 a-z와 0-9가 아닌 것을 공백으로 처리하고 arr에 담아준다.

    return arr == arr[::-1] # 리스트 arr과 뒤집어진 리스트 arr을 비교한 값을 리턴

array = input("문자열 입력: ")
print(solution(array))

여기서는 문자열 전체를 한 번에 영숫자만 걸러내도록 정규식으로 처리했다. 또한 파이썬은 문자열을 배열이나 리스트처럼 자유롭게 슬라이싱할 수 있는 좋은 기능을 제공하고, [::-1]을 이용하면 리스트를 뒤집을 수 있다. 슬라이싱은 내부적으로 C로 빠르게 구현되어 있어서 속도가 더 빨라진다는 장점이 있다.

알게된 점

데크 자료형을 이용하여 popleft( )를 수행할 경우 O(n) 속도가 보장된다는 것

파이썬에서 슬라이싱이 내부적으로 C로 구현되어 빠르다는 장점

공부할 것

정규식 re모듈의 기본 사용법 익히기

728x90