파이썬 큐와 스택 알고리즘 회문 찾기, palindrome #11

파이썬 큐와 스택 알고리즘 회문 찾기, palindrome #11

 

 

안녕하세요.

 

파이썬으로 공부하는 알고리즘 11번째 시간입니다.

 

오늘은 회문 찾기 문제입니다. 회문이란 조금 생소하게 들리실 수 있는데, "역삼역", "기러기", "일요일" 과 같이 앞으로 읽으나, 뒤로 읽으나 같은 말을 이야기합니다. 글자 사이의 공백이나 기호는 무시하고 앞으로 읽으나 뒤로 읽으나 같으면 회문이라고 합니다. 물론 영어에도 그런 단어들이 있겠죠? "mom" , "noon", "kayak", "wow", "level" 등이 있습니다.

 

 

회문인지 아닌지를 판별하려면 어떤 방법이 있을까요? 우리는 이번 회문 찾기 알고리즘에서 큐와 스택에 대해서 알아 볼것 입니다. 큐와 스택을 이용해서 회문 여부를 판별할 수 있습니다.

 

큐와 스택은 컴퓨터의 자료구조에서 기본적인 개념 입니다. 두 자료 구조는 자료를 넣거나, 혹은 빼거나의 개념입니다. 그리고 안에 있는 자료는 일렬로 보관되고 있다는 공통점이 있습니다. 하지만 왜 큐와 스택으로 구분되어 있을까요? 바로 넣고 빼는 로직이 다르기 때문입니다.

 

1. 큐 (queue)

큐는 줄 서기와 비슷 합니다. 우리가 버스를 타거나 어딘가 입장을 기다릴 때 줄을 서고 있습니다. 나중에 온 손님은 줄의 맨 뒤로 가서 줄을 섭니다. 버스를 탈 때는 제일 앞에서부터 타게 됩니다. 이것을 우리는 영어로 First In First Out으로 표현할 수 있습니다. 큐에 자료를 넣는 행위를 인큐(enqueue)라고 하고, 자료를 하나 빼내는 행위는 디큐(dequeue)라고 표현합니다.

 

2. 스택 (stack)

스택은 컵을 쌓는 것으로 비유할 수 있습니다. 하나의 컵을 뒤집어 바닥에 놓습니다. 그럼 그 위에 또 다른 컵을 쌓고.. 그렇게 컵을 10개를 쌓았다고 생각해봅니다. 그 상태에서 쌓인 컵 중에 하나를 젤 위에서 부터 뺍니다. 하나를 빼고 두 개를 빼고.. 이런 경우가 바로 스택 자료 구조입니다. 가장 나중에 쌓은 컵을 가장 먼저 꺼냅니다. 영어로는 Last In First Out이라 표현합니다. 스택에서 하나의 자료를 넣는 행위를 푸시(push)라고 하고, 자료를 하나 빼내는 행위는 팝(pop)이라 표현 합니다.

 

큐에서 자료를 꺼내면 들어간 순서 그대로 나오게 되지만, 스택에서 자료를 꺼내면 들어간 순서와 정 반대의 순서로 자료가 나오게 됩니다. 이젠 큐와 스택, 그리고 회문의 관련성을 이해하셨나요?

 

파이썬의 리스트는 위에서 언급한 큐와 스택을 만드는데 편리하게 사용됩니다. 앞에서 설명한 바와 같이 어떤 리스트에 [1,2,3,4]가 들어 있다면 큐와 스택을 이용해서 데이터를 꺼내온다면 아래 결과와 같을 겁니다.

큐 : [1,2,3,4]

스택 : [4,3,2,1]

 

이젠 여기에 숫자 대신 문자를 넣고 큐를 이용해 문자를 꺼낸 것과 스택을 이용해 문자를 꺼낸 값이 같다면 회문이 되는 거 겠죠. 당연한 이야기 겠지만 두 결과가 다르다면? 회문이 아닌 것이 되겠습니다.

 

이젠 위에서 설명한 알고리즘을 파이썬 코드로 구현해 보겠습니다.

# 주어진 문장이 회문인지 아닌지 찾기(큐와 스택의 특징을 이용)
# 입력: 문자열 s
# 출력: 회문이면 True, 아니면 False

def palindrome(s):
    # 큐와 스택을 리스트로 정의
    qu = []
    st = []
    # 1단계: 문자열의 알파벳 문자를 각각 큐와 스택에 넣음
    for x in s:
        # 해당 문자가 알파벳이면(공백, 특수문자, 숫자가 아니면)
        # 큐와 스택에 각각 그 문자를 추가
        if x.isalpha():
            qu.append(x.lower())
            st.append(x.lower())
    # 2단계: 큐와 스택에 들어 있는 문자를 꺼내면서 비교
    while qu:  # 큐에 문자가 남아 있는 동안 반복
        if qu.pop(0) != st.pop():  # 큐와 스택에서 꺼낸 문자가 다르면 회문이 아님
            return False

    return True

print(palindrome("Wow"))
print(palindrome("Madam, I’m Adam."))
print(palindrome("Madam, I am Adam."))

여기서 사용된 isalpha() 함수는 주어진 문자가 알파벳 문자에 해당하는지 확인을 하는 역할을 합니다. 공백, 숫자, 특수문자도 걸러냅니다. 물론 모든 문자를 소문자로 만들어 비교를 합니다. 그래야 대문자, 소문자를 가리지 않고 회문인지 아닌지를 판단할 수 있기 때문입니다.

 

회문 찾기 어떠셨나요?

 

생각보다 간단한 알고리즘이었습니다.

 

여기까지 읽어주신 여러분 감사합니다. 다음 시간에 또 찾아오겠습니다!

 

 

by.sTricky