หาเวลาที่สัญญาณใช้ถึงทุกตำแหน่งในสตริง (C++)

บทนำ

ในบทช่วยสอนนี้ เราจะคำนวณ เวลาที่สัญญาณ (signal) ใช้ในการแพร่ไปถึงทุกตำแหน่ง (position) ในสตริง

กฎของปัญหา

• สตริงประกอบด้วยตัวอักษร 's' (signal) และ 'p' (position) เท่านั้น
• สัญญาณเริ่มจาก 's' และแพร่ไปทั้งซ้ายและขวา
• ใช้เวลา 1 หน่วยต่อการเคลื่อนที่ 1 ตำแหน่ง
• หาเวลาขั้นต่ำที่ทำให้ 'p' ทุกตัวกลายเป็น 's'

ตัวอย่าง

Input: "pppppspss" → Output: 5
Input: "pspspsps" → Output: 1
Input: "ssssss" → Output: 0

อัลกอริทึม

1. วนลูปนับ 'p' ติดต่อกัน (p_count)
2. เมื่อเจอ 's' (หรือจบสตริง):
   • ถ้า p_count > time ปัจจุบัน:
   • ตรวจสอบว่ามี 's' ด้านซ้ายของบล็อก p นี้หรือไม่
   • ถ้ามี 's' ทั้งสองข้าง → เวลา = ceil(p_count / 2) (สัญญาณมาจาก 2 ทิศทาง)
   • ถ้ามี 's' ข้างเดียว → เวลา = p_count
   • อัปเดต time = max(time, ค่าที่คำนวณได้)
3. รีเซ็ต p_count = 0

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

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

int timeToConvertToSignalString(string sample_string, int string_len) {
    int p_count = 0, time = 0;
    
    for (int i = 0; i <= string_len; i++) {
        if (i < string_len && sample_string[i] == 'p') {
            p_count++;
        } else {
            if (p_count > time) {
                bool is_present_left_side = false;
                // ตรวจสอบว่ามี 's' ด้านซ้ายของบล็อก p นี้หรือไม่
                if ((i - p_count) > 0 && sample_string[i - p_count - 1] == 's') {
                    is_present_left_side = true;
                }
                
                if (is_present_left_side) {
                    p_count = ceil((double)p_count / 2);
                }
                time = max(time, p_count);
            }
            p_count = 0;
        }
    }
    return time;
}

int main() {
    string sample_string = "pppppspss";
    int n = sample_string.size();
    cout << timeToConvertToSignalString(sample_string, n) << endl;
    return 0;
}

ผลลัพธ์

5

คำอธิบายตัวอย่าง "pppppspss"

• บล็อกแรก: "ppppp" (5 p) ตามด้วย s → มี s ด้านขวา แต่ไม่มี s ด้านซ้าย (เป็นต้นสตริง) → เวลา = 5
• บล็อกที่สอง: "p" (1 p) ระหว่าง s...s → มี s ทั้งสองข้าง → เวลา = ceil(1/2) = 1
• ค่าสูงสุด = 5

สรุป

อัลกอริทึม O(n) หาเวลาสัญญาณแพร่ครอบคลุมทุกตำแหน่ง จุดสำคัญคือการจัดการบล็อก p ที่มี s ทั้งสองข้าง (เวลาลดครึ่ง) หากมีคำถาม สามารถถามได้ในส่วนความคิดเห็นครับ