โปรแกรมตรวจสอบอาร์เรย์เป็นพาลินโดรมหรือไม่โดยใช้ STL ใน C++

ภาพรวมปัญหา

โปรแกรมนี้ใช้ตรวจสอบว่าอาร์เรย์ของจำนวนเต็มเป็นพาลินโดรม (Palindrome) หรือไม่ โดยใช้ฟังก์ชันจาก STL (Standard Template Library) ใน C++ พาลินโดรมคือลำดับที่อ่านจากหน้าหรือหลังได้เหมือนกัน เช่น {1, 2, 3, 2, 1}

แนวคิด STL ที่ใช้

• memcpy - คัดลอกข้อมูลจากอาร์เรย์หนึ่งไปยังอีกอาร์เรย์หนึ่ง
• reverse - กลับลำดับองค์ประกอบในอาร์เรย์
• การเปรียบเทียบอาร์เรย์ต้นฉบับกับอาร์เรย์ที่กลับลำดับแล้ว

ขั้นตอนการแก้ปัญหา

1. สร้างอาร์เรย์สำรอง (copy) จากอาร์เรย์ต้นฉบับ
2. กลับลำดับอาร์เรย์ต้นฉบับด้วย reverse()
3. เปรียบเทียบแต่ละตำแหน่งระหว่างอาร์เรย์ที่กลับแล้วกับอาร์เรย์สำรอง
4. ถ้าทุกตำแหน่งตรงกัน → เป็นพาลินโดรม
5. ถ้ามีตำแหน่งใดตำแหน่งหนึ่งไม่ตรง → ไม่ใช่พาลินโดรม

ตัวอย่างโค้ด C++

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

void checkPalindrome(int arr[], int size) {
    int flag = 0;
    int arrCopy[size];
    memcpy(arrCopy, arr, size * sizeof(int));
    reverse(arr, arr + size);
    
    for (int i = 0; i < size; i++) {
        if (arr[i] != arrCopy[i]) {
            flag = 1;
            break;
        }
    }
    
    if (flag == 0)
        cout << "It's a palindrome\n";
    else
        cout << "It's not a palindrome\n";
}

int main() {
    int arr[] = {2, 3, 4, 3, 2};
    int size = sizeof(arr) / sizeof(arr[0]);
    checkPalindrome(arr, size);
    return 0;
}

ผลลัพธ์ตัวอย่าง

It's a palindrome

กรณีทดสอบเพิ่มเติม

ความซับซ้อนของอัลกอริทึม

• เวลา: O(n) - ต้องทำการคัดลอก กลับลำดับ และเปรียบเทียบ
• พื้นที่: O(n) - ต้องใช้อาร์เรย์สำรองขนาดเท่าอาร์เรย์ต้นฉบับ