이 글에서는 이중 연결 리스트(Doubly Linked List)를 이용해 주어진 문자열이 회문(Palindrome)인지 확인하는 방법을 알아봅니다.
회문 판별 알고리즘의 기본 개념
먼저 문자열의 각 문자를 하나의 이중 연결 리스트에 순서대로 삽입합니다. 그다음 left와 right라는 두 개의 포인터를 준비합니다.
left포인터는 리스트의 앞쪽(왼쪽)에서 시작합니다.right포인터는 리스트의 뒤쪽(오른쪽)에서 시작합니다.
양쪽 끝에서부터 동시에 스캔을 진행하며, left가 가리키는 문자와 right가 가리키는 문자가 서로 같다면 left는 다음 노드로, right는 이전 노드로 이동합니다. 만약 두 문자가 다르다면 즉시 false를 반환하여 회문이 아님을 알립니다.
이 과정은 left와 right가 같은 노드를 가리키게 되거나, right가 left의 바로 이전 노드를 가리킬 때까지 반복됩니다. 모든 비교가 통과되면 해당 문자열은 회문입니다.
C++ 구현 코드
#include <iostream>
using namespace std;
class Node {
public:
char data;
Node *next;
Node *prev;
};
void getNode(Node** start, char new_data) {
struct Node* newNode = new Node;
newNode->data = new_data;
newNode->next = (*start);
newNode->prev = NULL;
if ((*start) != NULL)
(*start)->prev = newNode ;
(*start) = newNode;
}
bool isPalindrome(Node *left) {
if (left == NULL)
return true;
Node *right = left;
while (right->next != NULL)
right = right->next;
while (left != right && right != left->prev) {
if (left->data != right->data)
return false;
left = left->next;
right = right->prev;
}
return true;
}
int main() {
Node* head = NULL;
string str = "madam";
for(int i = 0; i< str.length(); i++){
getNode(&head, str[i]);
}
if (isPalindrome(head))
cout << "This is Palindrome";
else
cout << "This is Not a Palindrome";
}코드 설명
1. 노드 생성 및 삽입 — getNode()
getNode() 함수는 새로운 노드를 생성하고, 이를 리스트의 맨 앞에 추가합니다. 새 노드의 next는 기존 시작 노드를 가리키고, 기존 시작 노드의 prev는 새 노드를 가리키도록 설정하여 이중 연결 구조를 유지합니다.
2. 회문 검사 — isPalindrome()
isPalindrome() 함수는 먼저 right 포인터를 리스트의 마지막 노드까지 이동시킵니다. 이후 left는 앞에서 뒤로, right는 뒤에서 앞으로 한 칸씩 이동하며 대칭 위치의 문자들을 비교합니다. 불일치가 발견되면 곧바로 false를 반환하고, 모든 비교가 끝나면 true를 반환합니다.
실행 결과
This is Palindrome
예제에서 사용한 문자열 "madam"은 앞에서 읽으나 뒤에서 읽으나 같은 회문이므로, 프로그램은 올바르게 회문임을 출력합니다.
복잡도 분석
- 시간 복잡도: O(n) — 문자열의 길이에 비례하여 노드를 삽입하고, 양쪽에서 한 번씩 스캔하므로 선형 시간이 소요됩니다.
- 공간 복잡도: O(n) — 문자열의 각 문자를 저장하기 위한 이중 연결 리스트가 필요합니다.