문자열이 회문(回文)인지 아닌지 판단하여 회문이면 True, 아니면 False를 결과로 알려 주는 알고리즘을 만들어 보세요.

 

이번에 풀어 볼 문제는 회문(回文, palindrome) 찾기 문제입니다.

회문은 조금 생소한 단어인데 ‘순서대로 읽어도 거꾸로 읽어도 그 내용이 같은 낱말이나 문장’을 뜻합니다. 낱말 사이에 있는 공백이나 문장 기호 등은 무시하므로 다음 낱말과 문장은 모두 회문입니다.

 

회문의 예(한글)	회문의 예(영어)
역삼역 기러기 일요일 사진사 복불복 다가가다 기특한 특기 다했냐? 했다! 다시 합창 합시다	mom wow noon level radar kayak racecar God’s dog Madam, I’m Adam.

 

어떤 문장이 주어졌을 때 이 문장이 회문인지 아닌지 판단하려면 어떻게 해야 할까요?

여러 가지 방법이 있지만, 여기서는 가장 기본적인 자료 구조인 큐와 스택을 알아본 다음, 큐와 스택의 특징을 이용해서 회문을 판단하는 방법을 살펴보겠습니다.