หาจำนวนเซกเมนต์ที่สมาชิกทุกตัวมากกว่า X ด้วย C++

ในบทความนี้ เราต้องหาจำนวนเซกเมนต์ (segments) หรือซับอาร์เรย์ (subarrays) ในลำดับที่กำหนด ที่สมาชิกทุกตัวมีค่ามากกว่าตัวเลข X ที่กำหนด

เราสามารถนับเซกเมนต์ที่ทับซ้อนกันได้เพียงครั้งเดียว และสองสมาชิกหรือเซกเมนต์ที่ติดกันไม่ควรนับแยกกัน ตัวอย่างพื้นฐานของปัญหานี้:

Input : arr[ ] = { 9, 6, 7, 11, 5, 7, 8, 10, 3}, X = 7 Output : 3 Explanation : { 9 }, { 11 } และ { 8, 10 } เป็นเซกเมนต์ที่มากกว่า 7
Input : arr[ ] = { 9, 6, 12, 2, 11, 14, 8, 14 }, X = 8 Output : 4 Explanation : { 9 }, { 12 }, { 11, 14 } และ { 14 } เป็นเซกเมนต์ที่มากกว่า 8

วิธีการหาคำตอบ

Naive Approach

ในปัญหานี้ เราเริ่มต้นตัวแปร state ด้วย 0 และเริ่มประมวลผลอาร์เรย์ที่กำหนด และเปลี่ยน state เป็น 1 เมื่อพบสมาชิกที่มากกว่า X และประมวลผลสมาชิกต่อไป และเปลี่ยน state กลับเป็น 0 เมื่อพบตัวเลขที่น้อยกว่าหรือเท่ากับ X และเพิ่ม count ด้วย 1 ทุกครั้งที่ state กลายเป็น 1 แล้วกลับมาเป็น 0

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

#include <bits/stdc++.h>
using namespace std;

int main() {
    int a[] = { 9, 6, 12, 2, 11, 14, 8, 14 };
    int n = sizeof(a) / sizeof(a[0]);
    int X = 8;
    int state = 0;
    int count = 0;
    
    // วนลูปผ่านอาร์เรย์
    for (int i = 0; i < n; i++) {
        // ตรวจสอบว่าสมาชิกมากกว่า X หรือไม่
        if (a[i] > X) {
            state = 1;
        } else {
            // หาก flag เป็นจริง
            if (state)
                count += 1;
            state = 0;
        }
    }
    
    // ตรวจสอบเซกเมนต์สุดท้าย
    if (state)
        count += 1;
    
    cout << "Number of segments where all elements are greater than X: " << count;
    return 0;
}

ผลลัพธ์

Number of segments where all elements are greater than X: 4

คำอธิบายโปรแกรม

ในโปรแกรมข้างต้น เราใช้ state เป็นสวิตช์ (switch) และตั้งค่าเป็น 1 เมื่อพบตัวเลขที่มากกว่า X และตั้งค่าเป็น 0 เมื่อพบตัวเลขที่น้อยกว่าหรือเท่ากับ X และสำหรับทุกครั้งที่ state กลายเป็น 1 แล้วกลับมาเป็น 0 เราเพิ่ม count ขึ้น 1 สุดท้าย พิมพ์ผลลัพธ์ที่เก็บไว้ใน count

สรุป

ในบทความนี้ เราแก้ปัญหาการหาจำนวนเซกเมนต์ที่สมาชิกทุกตัวมากกว่า X โดยใช้วิธีการตั้งค่า state เป็น 1 และ 0 ทุกครั้งที่พบเซกเมนต์ เราสามารถเขียนโปรแกรมนี้ในภาษาโปรแกรมมิ่งอื่นๆ เช่น C, Java, Python ได้เช่นกัน