Algorithm- 큐와 스택을 활용한 회문(똑바로 읽어도 거꾸로 읽어도 같은 단어나 문장) 찾기

1. 큐와 스택

스택과 큐 두 자료구조는 자료를 넣는 동작과 자료를 빼는 동작을 할 수있고

들어간 자료가 일렬로 보관된다는 공통점이 있다.

하지만 자료를 넣고 뺄때 동작하는 방식이 서로 다르다.

 

1) 큐: 큐는 택시를 타기 위해서 줄을 서는 과정에 비유할 수 있다.

        우리가 일상 생활에서 택시 정류장에서 택시를 탈때를 생각해보면

        새로 택시 정류장에 도착한 사람은 맨 뒤로 가서 줄을 서고

        택시가 도착하면 그 줄의 맨 앞에 선 사람이 줄을 빠져나가 택시를 탄다.

        즉 먼저 줄을 선 사람이 가장 먼저 택시를 타게 된다. ( First In First out )

       즉 큐에서 자료를 꺼낼때는 자료가 들어간 순서대로 나온다.

 

2) 스택: 스택은 접시 쌓기에 비유할 수 있다.

          식당에서 접시를 차곡차곡 쌓았다가 하나씩 꺼내 설거지하는 과정을 생각해보면

          다 먹은 접시를 쌓을때는 샇은 접시 맨 위에 올려 놓고

          설거지를 하려고 접시를 꺼낼 때도 맨 위에 있는 접시부터 꺼낸다.

          즉 가장 마지막에 들어간 자료를 가장 먼저 꺼내는 것을 의미한다. ( Last in First out )

          그리고 맨 아래에 있는 접시를 꺼내려면 맨 위에 있는 접시부터 하나 하나 꺼내야

          한다는 것도 이해할 수 있다.

 

 

만약 1, 2, 3, 4, 5라는 자료가 있을때 큐와 스택에서 차례대로 자료를 빼내면 각각

1, 2, 3, 4, 5와 5, 4, 3, 2, 1 순서로 자료가 나오게 되는데 이것이 바로 회문을 판단하는데

필요한 큐와 스택의 특징이다.

주어진 문장의 문자들을 하나하나 큐와 스택에 넣은 다음 큐와 스택에서 하나씩 자료를

꺼낸다고 생각해볼때 

큐는 들어간 순서 그대로 스택은 들어간 순서와 반대로 문자들이 뽑혀 나오게 된다.

회문은 거꾸로 읽어도 같은 글자가 나와야 된다. 따라서 큐에서 꺼낸 문자들(원래 순서)이

스택에서 꺼낸 문자들(역순)과 모두 같다면 그 문장은 회문이다.

 

이런 큐와 스택의 특징으로 회문 찾기 알고리즘을 만들어보면 아래와 같다.

 

2. 회문 찾기 알고리즘

# 주어진 문장이 회문인지 아닌지 찾기 (큐와 스택의 특징을 이용)
# 입력: 문자열 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("Iam a programer"))

 

실행 결과