문자열이 회문인지 아닌지 판단하여 회문이면 true, 아니면 false를 결과로 알려주는 알고리즘을 만들기

• 회문(回文,palindrome)
  : 순서대로 읽어도 거꾸로 읽어도 그 내용이 같은 낱말이나 문장(낱말 사이에 공백이나 문장기호등은 무시)
• 큐와 스택을 이용하여 풀어보기

큐와 스택

• 공통점:'자료를 넣는 동작'과 '자료를 빼는 동작'을 할 수 있음.
  들어간 자료가 일렬로 보관됨.

큐

줄서기에 비유 할수 있다. 택시를 타기 위해 먼저 서있던 사람이 줄을 빠져나가 택시를 타는 것과 같다. = first in first out

큐에 자료 한개를 집어넣는 동작:인큐(enqueue)
큐안에 자료 한개를 꺼내는 동작:디큐(dequeue)

스택

접시 쌓기에 비유 할수 있다. 맨아래있는 접시(=처음 들어간 자료)를 꺼내기 위해 맨위의 접시(=가장 나중에 들어간 자료)를 먼저 차근 차근 꺼내야 한다.(기교금지!ㅋㅋ)
=last in firat out.

스택에 자료 하나를 집어 넣는 동작:푸시(push)
스택안에 인에 있는 자료를 하나 꺼내는 동작:팝(pop)

큐와 스택에서 자료를 꺼내면 큐는 그대로 1,2,3,4가 나오는 반면 스택은 4,3,2,1 순서로 자료가 나온다.

리스트로 큐와 스택 사용하기

큐와 스택은 자료를 일렬로 보관하는 특징이 있다-> 파이썬'리스트'를 이용해서 쉽게 만들어 볼수 있습니다.

밑의 표와 같은 방식을 이용해 큐와 스택을 만들어보자.

회문찾기 알고리즘

1)주어진 문장을 하나하나 큐와 스택에 넣는다
2)큐와 스택에서 하나씩 자료를 꺼낸다. 큐는 순서대로 스택은 끝에서 부터 문자가 뽑혀나온다.
3)큐에서 꺼낸 문자==스택에서 꺼낸 문자면 그 문자는 회문이다!

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

def palindrom(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(palindrom("Wow"))
print(palindrom("Madam,I'm Adam"))
print(palindrom("Madam,I am Adam."))

• .isalpha()함수 주어진 문자가 알파벳 문자에 해당하는지 확인하는 기능
  lower()함수:주어진 알파벳을 소문자로 바꾸는 기능.

틀린답

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

def palindrom(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(palindrom("Wow"))
print(palindrom("Madam,I'm Adam"))
print(palindrom("Madam,I am Adam."))

\

다 true가 나오는 데 책에는 마지막게 false가 나온다고 써있음.

원인 while문을 들여썼다.

11-1 :큐와 스택을 활용하지 않고 회문검사하기

#주어진 문장이 회문인지 확인(문자열의 앞뒤를 서로비교)
#입력 문자열s
#출력:회문이면 true,아니면 false

def pailndrome(s):
    i=0 #문자열의 앞에서 비교할 위치
    j=len(s)-1 #문자열의 뒤에서 비교할 위치
    while i<j:
        if s[i].isalpha()==False: #중간까지만 검사하면됨
            i+=1
        #j위치에 있는 문자가 알파벳 문자가 아니면 앞으로 이동
        elif s[j].isalpha()==False:
            j-=1
            #i와 j위치에 둘다 알파벳이 있으면 두 문자르 비교하고 다르면 회문이 아님
        elif s[i].lower() != s[j].lower():
            return False
        #i와 j위치에 두문자를 비교하고 같으면 다음 비교대상으로 넘어감
        else:
            i+=1
            j-=1
    return True

print(pailndrome("Wow"))
print(pailndrome("Madam,I'm Adam"))
print(pailndrome("Madam,I am Adam"))