[파이썬 알고리즘 인터뷰 ] 문자열 조작_유효한 팰린드롬

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

 

EX1_입력 ] "A man, a plan, a canal : Panama"
EX1_출력 ] true

EX2_입력 ] "race a car"
EX2_출력 ] false

 

팰린드롬 이란?!

- 팰린드롬이란 앞뒤가 똑같은 단어 / 문장을 말합니다. 즉! 뒤집어도 같은 말이 된다. 우리말로는 '회문'이라고 하며 대표적 예시로는 "소주 만 병만 주소"가 있다. 

 

해당 문제를 푸는 방법?!

1. 리스트로 변환

2. 데크 자료형 사용

3. 슬라이싱 사용

4. C로 구현

 

방법 1. 리스트로 변환 

실행 시간 : 304 밀리초

# Palidndrome
class Test:
    def isPalindrome (self, s:str)-> bool :
        # strs : List[str] = [char.lower() for char in s if char.isalnum()]
        strs = []
        for char in s:
            if char.isalnum(): #isalnum()은 영문자, 숫자 여부를 판별하는 함수!
              strs.append(char.lower()) #대소문자 구분 안하므로 모두 소문자 변환!

	 	#팰린드롬 여부 판별 
        while len(strs)>1 :
            if strs.pop(0) != strs.pop(): #리스트는 pop() 사용 가능
                return False
        return True

test = Test()
test.isPalindrome("hello")

 

- isalnum() 함수를 사용하여 조건에 맞는 영문자와 숫자만을 추출해 리스트 str에 집어넣는다. 그 후 str 리스트의 양 끝을 pop() 하면서 팰린드롬 여부를 파악한다. ( 리스트의 길이가 1 이상일때까지 pop / 1이면 한개 밖에 안남아서 양 끝 비교  X )

 

 

방법 2. 데크 자료형을 사용 ( 최적화 )

실행 시간 : 64밀리초

import collections
class Test :
    def isPalindrome(self, str):
            strs : Deque = collections.deque()
            
            for char in str :
                if char.isalnum():
                    strs.append(char.lower())
            
            while len(strs)>1 :
                if strs.popleft() != strs.pop():
                    return False 
            return True

test = Test()
testcase= "A man, a plan, a canal : Panama"
result= test.isPalindrome(testcase)
print(result)

 

- 리스트 대신 데크를 사용해서 해결한 방법이다. 데크를 사용하면 리스트 보다 좀 더 속도를 높일 수 있다. 

- 리스트의 경우 pop(0)가 O(n)인 반해 데크는 popleft가 O(1)이어서 n 번씩 도는 반복문에서 리스트는 총 O(n^2), 데크는 O(n)의 성능을 가진다.

 

데크( Deque )란?
- 데크는 양방향 큐를 말한다. 보통 큐의 경우 선입선출 방식으로 작동하지만 데크는 앞,뒤 양쪽 방향에서 요소를 추가/ 제거 할 수 있다. 데크는 양 끝 요소들의 append와 pop의 속도가 빠르다. 

 

 

방법 3. 슬라이싱 사용

실행시간 : 36밀리초

import re #re.sub 정규표현식 사용을 위해
class Test:
    def isPalindrome(self, str):
        str = str.lower()
        str = re.sub('[^a-z0-9]','',str) # re.sub(정규표현식, 바꿀 문자열, 대상 문자열)
        return str==str[::-1]

test=Test()
print(test.isPalindrome("abba"))

 

 

- 문자열을 조작할 수 있는 슬라이싱을 사용하여 문제를 해결했다. 정규식을 사용하여 불필요한 문자열을 제거하고 문자열을 뒤집어 기존 문자열과 같은지를 비교한다.

- 코드가 줄고 내부적으로 C로 구현되어있어 성능이 좋다. ( 파이썬 내부는 C언어로 구현 )

 

문자열 슬라이싱 ?!
- 문자열을 조작하기 위한 방법으로 파이썬이 제공하는 기능 중 하나이다. 내부적으로 매우 빠르게 작동하며 속도 개선에 매우 유리하다. 문자열을 별도의 리슽로 매핑하는 등의 처리에는 좋은 방법이지만 별도 자료형으로 매핑하는 과정에는 많은 연산 비용이 필요하므로 좋은 방법이 아닐 수 있다. 대부분의 문자열 작업은 슬라이싱으로 처리하는 편이 좋다.

 

 

방법 4. C 언어로 구현

실행시간 : 4밀리초

#define _CRT_SECURE_NO_WARNINGS    // scanf 보안 경고로 인한 컴파일 에러 방지
#include <stdio.h>
#include <string.h>
#include <stdbool.h>

int main()
{
    char word[30];               // 단어를 저장할 배열
    int length;                  // 문자열 길이
    bool isPalindrome = true;    // 회문 판별값을 저장할 변수, 초깃값은 true

    printf("단어를 입력하세요: ");
    scanf("%s", word);

    length = strlen(word);    // 문자열의 길이를 구함
    
    // 0부터 문자열 길이의 절반만큼 반복
    for (int i = 0; i < length / 2; i++)
    {
        // 왼쪽 문자와 오른쪽 문자를 비교하여 문자가 다르면
        if (word[i] != word[length - 1 - i])
        {
            // 회문이 아님
            isPalindrome = false;
            break;
        }
    }

    printf("%d\n", isPalindrome);    // 회문 판별값 출력

    return 0;
}

//출처 : https://dojang.io/mod/page/view.php?id=399

 

- C와 같은 컴파일 언어는 파이썬 같은 인터프리터 언어에 비해 성능이 좋다.

- 코드는 길지만 위치 포인터를 직접 조작할 수 있기에 실행속도가 빠르다.

 

 

---

[ 참고자료 ]

- 도서 : 파이썬 알고리즘 인터뷰