[4.16] 문제 13. 회문 찾기(큐와 스택)

<모두의 알고리즘 with 파이썬> 넷째 마당 - 자료구조

 

문제 13. 회문 찾기(큐와 스택)

 

회문 : 뒤집어도 똑같은 글자, 문장(일요일, 스위스, 기러기 등)

 

큐queue : '줄 서기'

앞 [A B C D] 뒤

인큐 enqueue : 앞 [A B C D E] 뒤

디큐 dequeue : 앞 [B C D E] 뒤 (A)

 

스택 stack  : '접시 쌓기'

Last in First Out

푸시 push 처음 [A B C D E] 끝

팝 pop 처음 [A B C D] 끝 (E)

 

리스트로 큐/스택 만들기

queue : qu.append(x), qu.pop(0)

stack : st.append(x), st.pop()

 

Q. 주어진 문장은 회문인가? 

def palindrome(s):
  qu = []
  st = []
  for x in s:
    #주어진 글자가 알파벳인지 확인
    if x.isalpha():
      qu.append(x.lower()) #소문자로 바꿈
      st.append(x.lower())
  while qu:
    if qu.pop(0) != st.pop():
      return False
  return True

print(palindrome("WoW"))

연습문제

- 큐, 스택 없이 회문 찾기

def palidrome(s):
  n = len(s)
  for i in range(1, n//2-1):
    if s[i] != s[-i]:
      return False
  return True

s = 'heeeh'
print(palidrome(s))
#풀었다 ~.~

#예제 코드...
def palindrome(s):
  i = 0
  j = len(s) -1
  while i < j :
    if s[i].isalpha() == False:
      i += 1
    elif s[j].isalpha() == False:
      j -= 1
    elif s[i].lower() != s[j].lower():
      return False
    else:
      i += 1
      j -= 1
  return True