(이상한 변호사 우영우)[python] 우영우 역삼역 '회문' 판독기

기러기 스위스 토마토 인도인 별똥별 우영우 역삼역 

제가 군대에있을때 방영했던 드라마였는데 그때 한참 부대 인사법이 우 to the 영 to the 우~ 였던 기억이 나네요 (그거하고 다니다가 행보관님한테 걸리면 '이야~ 심심한가보네? 장갑끼고 나와라 풀뽑으러 가자' 제초엔딩)

얼마전에 유튜브로 요약본을 보는데 (박은빈은 그냥 미쳤다 지성과 미모를 두루갖춘 진정한 팔방미인) 우영우의 대사중 "제이름은 똑바로 읽어도 거꾸로 읽어도 우영우입니다 기러기 스위스 토마토 인도인 별똥별 우영우 .... 역삼역..?"이라는 대사가 나옵니다. 우영우의 말대로 똑바로 읽어도 거꾸로 읽어도 같은 단어를 회문(Palindrome, 펠린드롬)이라고 합니다.

회문의 예시는 많습니다. 제가 초등학생때 유행한 슈퍼주니어의 노래 '로꾸거'가사에서도 많이 찾아볼수있는데요

"여보게 저기 저게보여" "여보 안경안보여" "다시 합창합시다" 등 (지금 생각해보면 가사쓰기 힘들었을거같음;;;) 신기한 회문이 많이 있죠. 

갑자기 우영우보다가 회문에 꽃힌이유는.. 최근 알고리즘을 공부하다 회문을 예시로 들며 알게된 개념(?)이 있는데요 이번 글에는 그에대한 얘기를 해보겠습니다.

 

어떤 문자열을 입력받았을때 이 단어가 회문인지 아닌지 판독해주는 프로그램을 짠다고 해봅시다. 회문인경우 1, 회문이 아닌경우 -1을 출력한다고 했을때 abba를 입력하면 1, aqewrjq을 입력하면 -1이 출력되어야겠죠.

 

s = str(input())

def is_palindrome(s):
    return s == s[::-1]

if is_palindrome(s):
    print("1")
else:
    print("-1")

간단한 방식입니다. 회문판독의 기본 방식은 우영우가 말했듯 "똑바로 읽어도 거꾸로 읽어도"에 있습니다.

즉 문자열을 입력받은 순서대로 정렬한것과, -1부터 뒤집어서 정렬한것이 같다면 회문인겁니다.

위와같은 방식으로 원본 문자열과 -1부터 뒤집은 문자열이 같다면 True가 할당되므로 if문에 걸려 1이 출력되죠.

 

출력예시

위는 출력예시입니다. 한글회문도(붙여쓰기 한다는 가정하에) 동작이 됩니다.

 

회문을 출력하는 또 다른 다소 복잡한 방식이있는데요.. 이 개념은 알고리즘을 공부할때 자주 나타나는 개념이므로 이참에 한번 정리해보겠습니다. 바로 큐(queue)와 스택(stack)입니다. 

 

큐와 스택은 그냥 자료를 저장하고 추출하는 방식입니다. 큐는 선입선출, 스택은 후입선출 방식인데요.

예를 들자면 큐는 놀이기구 대기줄과 같습니다. 먼저 줄에 선 사람부터 먼저 자이로드롭을 탈수있는거죠. (주말에 매직패스없이 롯데월드에 가면 아주 멋진 큐를 경험할수있습니다.) 스택은 말그래도 쌓는것. 예를들자면 회전초밥집에서 설거지 알바를할때 접시가 산처럼 쌓여있는 상황입니다. 이때 먼저 들어온 접시 위에 계속 접시를 쌓게되죠. 가장 최근에 들어온 접시는 접시탑 제일위에 위치할겁니다. 알바가 설거지를 할때 큐의 방식처럼 선입선출을 하면 어떻게될까요? 넌 제일 먼저들어왔으니 제일먼저 씻겨줄게~ 해버리면 접시탑이 무너지며 대참사가 일어나겠죠. 이때 사용하는게 스택입니다.

제일 늦게 들어온것을 제일먼저 꺼내주는것이죠.

 

큐와 스택 이미지 설명

큐와 스택을 이미지로 표현해봤습니다. 큐에 자료를 삽입하는것을 enqueue, 추출하는것을 dequeue라고 하고, 스택에 자료를 삽입하는것을 push, 추출하는것을 pop라고 합니다. 이렇게 보니 우영우 역삼역을 큐와 스택으로 어떻게 판독할지 대충 감이 오시나요? 바로 큐에서 빼낸 우영우와 스택에서 빼낸 우영우 문자열이 같다면 그 단어는 회문이겠죠.

 

큐와 스택은 외부모듈 (from collections import deque) 데크를 불러와 생성하는게 더 효율적입니다. 그러나 모듈없이 리스트만으로도 구현이 가능한데요..

 

q=[]
q.append(x)
x=q.pop(0)

st=[]
st.append(x)
x=st.pop()

그냥 보통 알고있는 리스트에 자료를 입력해 순서대로/역순으로 빼내는 코드입니다. 여기에 그냥 큐, 스택이라는 명칭만 붙인거죠. 자료 입력은 같이 받지만 빼낼때 큐는 pop(0)을 지정해주며 리스트상 가장 앞에있는 자료를 추출합니다. 스택은 pop에 값을 지정해주지 않으므로 기본값인 뒤에서부터 추출하는 동작을 수행합니다.

 

 

s=str(input())
q=[]
st=[]
TF_list=[]

for x in s:
    q.append(x)
    st.append(x)

while q:
    if q.pop(0)!=st.pop():
        TF_list.append('F')

            
if 'F' not in TF_list:
    print("%s는 회문입니다."%s)
    
else:
    print("%s는 회문이 아닙니다."%s)

큐와 스택의 개념을 이용해 짜본 회문판독 코드입니다. 사실 위에 문자열을 뒤집는 코드가 훨씬 간단하죠?;;

문자열 s를 입력받아 for문을 이용해 s를 구성하는 문자(문자, 공백, 특수문자)를 모두 큐와 스택에 넣어줍니다.

예를들자면 우영우역삼역을 입력했을때 큐와 스택 모두 ['우','영','우','역','삼','역']이 됩니다. 이제 큐와 스택에서 각각 선입선출, 후입선출 방식으로 비교해줍니다. 큐는 우영우역삼역순으로 , 스택은 역삼역우영우 순으로 비교를하는거죠.

이때 추출된 자료가 같지 않다면 True/False를 판별해주는 TF_list에는 F가 추가됩니다.

 

이걸 한 이유는 ... 문자열을 리스트로받아 한글자 한글자 비교하기때문에 글자별로 True, False가 계속 바뀝니다.

예를들어 '우영우이상한변호사우영우'라는 문자열을 입력받았을때 큐와 스택에서 각각 0,1,2번째 추출은 True를 출력하지만 3~8번째 추출은 '이상한변호사'와 '사호변한상이'의 비교이므로 False를 출력합니다. 그래서 그냥 단순하게 문자열 검사 중 False를 한번이라도 포함한다면 회문이 아닌것으로 판단한다는 의미에서 TF_list를 따로 구성한겁니다.

 

결국 마지막 if문은 TF_list를 기준으로 회문인지 아닌지를 판단하는것이죠. TF_list에 F가 'not in' 즉, 하나도 없다면 (큐와 스택 비교에서 False가 한번도 발생하지 않았다면) 회문으로 판단하는것이죠. 그 결과는 아래와같습니다.

 

회문판독결과

제가 앞에서 한글판독할땐 띄어쓰기가 없는경우 정확한 판독이 가능하다고 했는데 그 이유를 설명드리겠습니다.

위에 출력결과를 보시면 '다시 합창합시다'는 회문이 아닌것으로 판단하지만 '다시합창합시다'는 회문으로 판단합니다. 문자열은 공백을 포함하기때문입니다. 공백을 포함하지 않고 회문판독을 하려면 is.alpha 함수를 이용하면 됩니다. 문자열에서 알파벳만 출력해서 큐와 스택에 넣을수있죠.

 

우영우 요약영상을 보다가 갑자기 큐 스택까지 ;;; 이런것도 생활속 코딩으(어거지)로 넣을수있겠죠? ㅋㅋ

쨌든 회문판독 자체만을 봤을땐 큐 스택이 마냥 효율적인 방식은 아닌것같군요;; 자주쓰이는 개념이긴하니 이 기회에 좀 숙지는 해놔야겠읍니다. 저는 다시 우영우 보러 가보겠습니다.