[ALGORITHMS]문제 13 회문 찾기

문제 13

회문 찾기

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

이번에 풀어 볼 문제는 회문 찾기 문제입니다.

회문은 조금 생소한 단어인데 순서대로 읽어도 거꾸로 읽어도 그 내용이 같은 낱말이나 문장'을 뜻합니다.

낱말 사이에 있느 공백이나 문장 기호 등은 무시하므로 다음 낱말과 문장은 모두 회문입니다.

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

1. 큐와 스택

두 자료 구조는 자료를 넣는 동작과 자료를 뺴는 동작을 할 수 있으며, 들어간 자료가 일렬로 보관된다는 공통점이 있습니다.

하지만 자료를 넣고 뺼 때 동작하는 방식이 서로 다릅니다.

* 큐

큐는 '줄 서기'에 비유할 수 있습니다. 택시를 타기 위해서 줄을 서는 과정을 떠올려 봅시다.

새로 택시 정류장에 도착한 사람은 맨 뒤로 가서 줄을 서고, 택시가 도착하면 그 줄의 맨 앞에 선 사람이 줄을 빠져나가 택시를 탑니다. 가장 먼저 줄을 선 사람이 가장 먼저 택스를 타게 됩니다(First In First Out)

- 큐에 자료를 한 개 집어 넣는 동작을 인큐(enqueue), 큐 안에 있는 자료를 한개 꺼내는 동작을 디큐(dequeue)라고 표현합니다.

*스택

스택은 '접시 쌓기'에 비유할 수 있습니다. 식당에서 접시를 차곡차곡 쌓았다가 하나씩 꺼내 설거지하는 과정을 생각해 봅시다. 다 먹은 접시를 쌓을 때는 쌓은 접시 맨 위에 올려놓습니다. 가장 마지막에 들어간 자료를 가장 먼저 꺼내는 것을 의미합니다.(Last In First Out)

- 스택에 자료를 하나 집어넣는 동작을 푸시(push) , 스택 안에 있는 자료를 하나 꺼내는 동작을 팝(pop)이라고 표현합니다

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

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

2. 회문 찾기 알고리즘

앞에서 자료 값 1,2,3,4가 들어 있는 큐와 스택에서 차례로 자료를 빼내면 각각 1,2,3,4와 4,3,2,1 순서로 자료가 나온다고 배웠습니다 이것이 바로 회문을 판단하는 데 필요한 큐와 스택의 특징입니다.

주어진 문장의 문자들을 하나하나 큐와 스택에 넣은 다음 큐와 스택에서 하나씩 자료를 꺼낸다고 생각해 봅시다. 큐가 들어간 순서 그대로, 스택은 들어간 순서와 정반대로 문자들이 뽑혀 나옵니다.

따라서 큐에서 꺼낸 문자들(원래 순서)이 스택에서 꺼낸 문자들(역순)과 모두 같다면 그 문장은 회문입니다.

* 회문 찾기 알고리즘

* 연습문제 

13-1 큐와 스택을 이용하지 않고 회문인지 아닌지 판단할 수 있는 방법이 있습니다.

문장의 앞뒤를 차례로 비교하면서 각 문자가 같은지 확인하는 방법입니다.

이 방법으로 회문인지 아닌지 판단하는 알고리즘을 만들어보세요

읽어주셔서 감사합니다.