[Python algorithm interview] 파이썬 기초 정리

파이썬 알고리즘 인터뷰에 대한
필자의 리뷰 및 테스트 예제입니다.

 

 

파이썬 알고리즘의 기초문제, 문자열부터 시작합니다.

앞전의 내용은 파이썬의 기본적인 내용에 대해서 다루고 있었습니다만

필자의 전 글에서 제시한 내용과 유사하므로 생략했습니다.

다만, 시간복잡도에 대한 내용은 유용한 것으로 보입니다.

 

 

멈춰있는 version

 

난이도 1의 문자열 문항입니다.

 

 

1. 유효한 펠린드롬 구해보기

 

🎈문제

 

주어진 문자열이 펠린드롬인지 확인하라. 대소문자를 구분하지 않으며, 

영문자와 숫자만을 대상으로 한다.

 

🔑입력 예제

 

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

true

 

펠린드롬이란?

 

코딩테스트에 설명없이 처음보는 단어가 계속 등장한다면 여간 당황스러운 일이 아닐 것입니다.

펠린드롬이란 앞에서 부터 읽어도, 뒤에서 부터 읽어도 같은 문장이 되는 것을 의미합니다.

작년 큰 인기를 끌었던 '이상한 변호사 우영우'가 좋은 예입니다.

우영우가 자기소개를 할 때 말하는 것이 모두 펠린드롬 자체 입니다.

 

기러기, 토마토, 스위스, 인도인, 별똥별

 

이러한 형태를 다른말로는 '회문'이라고 합니다.

 

예문에서 소개했던 'A man, a plan, a canal: Panama'도 거꾸로 하면

'a man a Plan a ca,nal panamA',  'a man a plan a canal panama'  그대로 됩니다.

 

우영우도 사실 본인의 이름보다도 펠린드롬을 계속 소개하고 다녔던 것이 아닐까요?

 

---

다시 돌아와서, 문자열을 직접 입력받아서 해당 문자열이 펠린드롬인지 아닌지를 판단해봅니다.

isalnum()을 사용해서 영문자, 숫자인지 여부를 확인해줍니다.

 

strs = []
for char in s:
    if char.isalnum():
       strs.append(char.lower())

 

 

그리고 while문을 사용해서 strs가 1보다 큰 상황에서, 맨 앞의 값을 계속 가져오는 pop(0)을 사용합니다.

그리고 pop() 결과와 같은지 확인해서 일치하지 않으면 False, 일치하면 True를 리턴합니다.

 

strs = []
for char in s:
    if char.isalnum():
       strs.append(char.lower())
       
    while len(strs) > 1:
          if strs.pop(0) != strs.pop():
             return False
    return True

 

함수는 isPalindrome으로 정했습니다.

 

def isPalindrome(s:str):
    strs = []
    for char in s:
        if char.isalnum():
            strs.append(char.lower())
       
    while len(strs) > 1:
        if strs.pop(0) != strs.pop():
            return False
        
    return True

---

 

그 외에도 데크 자료형과 슬라이싱을 사용한 방식을 제시하고 있습니다만

슬라이싱은 정규 표현식의 개념이 들어가기 때문에 여기서는 생략하려 합니다.

 

👇 Deque 자료형을 이용한 풀이사례

 

import collections
def isPalindrome(s: 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

 

Deque와 collections를 사용합니다.

 

* 초판 1쇄 기준 import collections가 빠져있는 에러가 있었습니다
collections는 파이썬의 특수 컨테이너 데이터형을 지원하는 모듈입니다.
자세한 자료는 https://docs.python.org/ko/3/library/collections.html

다행히 책만출판사의 github상에서는 완성된 풀이를 보실 수 있습니다.
http://algorithm-interview/1-2.py at master · onlybooks/algorithm-interview (github.com)

collections — Container datatypes

 

Deque를 사용하면 실행시간을 약 1/5가량으로 낮출 수 있습니다.

최적화를 요구하고 있지는 않지만, 시간이 촉박하게 주어지는 문제에서는 유용하게 사용할 수 있겠죠.

 

다음 시간에는 추가적인 문제풀이를 보겠습니다.