เพิ่มค่าตัวเลขสูงสุดโดยแทนที่ช่วงหลักติดต่อกันด้วยหลักทางเลือกใน C++

งานคือเพิ่มค่าตัวเลข N (ที่มีหลายหลัก) ให้มากที่สุดโดยแทนที่หลักของมันด้วยหลักทางเลือกจากอาร์เรย์ arr[10] โดย arr[d] คือหลักทางเลือกสำหรับหลัก d (0-9)

เงื่อนไขสำคัญ: แทนที่ได้เฉพาะ ช่วงติดต่อกัน (contiguous segment) เพียงช่วงเดียว และ ทำได้เพียงครั้งเดียว

ตัวอย่าง

ตัวอย่างที่ 1

Input: N = "1234", arr[] = {3,0,1,5,7,7,8,2,9,4}

Output: 1257

คำอธิบาย:

• หลัก 3 → ทางเลือก arr[3]=5 (ดีกว่า 3) ✓
• หลัก 4 → ทางเลือก arr[4]=7 (ดีกว่า 4) ✓
• หลัก 1,2 → ทางเลือกไม่ดีกว่า (arr[1]=0, arr[2]=1) ✗
• → แทนที่ช่วง "34" → "57" ได้ "1257"

ตัวอย่างที่ 2

Input: N = "5183", arr[] = {3,0,1,5,7,7,8,2,9,4}

Output: 7183

คำอธิบาย: หลัก 5 → arr[5]=7 (ดีกว่า) ✓ แต่หลักถัดไป 1 → arr[1]=0 (แย่กว่า) ✗ → แทนที่แค่หลักแรกได้ "7183"

แนวทางแก้ปัญหา (Greedy)

1. เดินจากซ้ายไปขวา หาหลักแรกที่ arr[d] > d (ทางเลือกดีกว่า)
2. จากตำแหน่งนั้น เริ่มแทนที่ต่อเนื่องไปขวา ตราบใดที่ arr[d] >= d (เท่าก็ได้ เพื่อต่อเนื่อง)
3. หยุดเมื่อเจอหลักที่ทางเลือกแย่กว่า (arr[d] < d) หรือจบสตริง
4. คืนค่าสตริงที่แก้ไขแล้ว

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

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

string maximizeNumber(string str, const int arr[10]) {
    int n = str.length();
    
    for (int i = 0; i < n; i++) {
        int digit = str[i] - '0';
        if (digit < arr[digit]) {  // พบหลักที่ทางเลือกดีกว่า
            int j = i;
            // แทนที่ต่อเนื่องตราบใดที่ทางเลือกดีกว่าหรือเท่า
            while (j < n) {
                int d = str[j] - '0';
                if (d <= arr[d]) {
                    str[j] = '0' + arr[d];
                    j++;
                } else break;
            }
            return str;  // ทำได้ครั้งเดียว จบเลย
        }
    }
    return str;  // ไม่มีการแทนที่
}

int main() {
    string str = "2075";
    int arr[] = {3, 0, 1, 5, 7, 7, 8, 2, 9, 4};
    cout << "Result: " << maximizeNumber(str, arr) << endl;
    return 0;
}

ผลลัพธ์

Result: 2375

2→arr[2]=1 (แย่กว่า) ข้าม, 0→arr[0]=3 (ดีกว่า) เริ่มแทนที่: 0→3, 7→arr[7]=2 (แย่กว่า) หยุด → "2375"

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

ความซับซ้อน

• เวลา: O(n) – เดินผ่านสตริงครั้งเดียว
• พื้นที่: O(1) – แก้ไข in-place