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

งานคือเพิ่มค่าตัวเลข A ให้มากที่สุดโดยแทนที่หลักบางหลักด้วยหลักจากตัวเลข B หากไม่สามารถเพิ่มค่าได้ ให้คงค่าเดิม เงื่อนไข: หลักจาก B ใช้ได้ครั้งละ 1 ตัวเท่านั้น

ตัวอย่าง

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

Input: A = "1221", B = "1211"

Output: 2221

คำอธิบาย: เลือก '2' จาก B แทน '1' ตัวแรกของ A → ได้ 2221 (แทนที่ครั้งเดียวเพราะ B มี 2 เพียงตัวเดียว)

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

Input: A = "1002", B = "3200"

Output: 3202

คำอธิบาย: เรียง B: 0023 → ใช้หลักใหญ่สุด (3,2) แทนหลักเล็กของ A จากซ้ายไปขวา

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

1. เรียงหลักของ B จากน้อยไปมาก (ascending)
2. เดินผ่าน A จากซ้ายไปขวา (หลักสำคัญสุดก่อน)
3. เดินผ่าน B จากขวาไปซ้าย (หลักใหญ่สุดก่อน)
4. ถ้า B[j] > A[i] ให้แทนที่ A[i] = B[j] แล้ว i++, j--
5. หาก B[j] <= A[i] ให้ i++ ต่อ (ไม่แทนที่)
6. หยุดเมื่อ j < 0 (ใช้หลัก B หมด) หรือ i == len(A)

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

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

string maximizeValue(string A, string B) {
    sort(B.begin(), B.end());  // เรียงน้อยไปมาก
    int i = 0, j = B.length() - 1;
    
    while (i < A.length() && j >= 0) {
        if (B[j] > A[i]) {
            A[i] = B[j];
            j--;
        }
        i++;
    }
    return A;
}

int main() {
    string a = "1204";
    string b = "4521";
    cout << maximizeValue(a, b) << endl;
    return 0;
}

ผลลัพธ์

5424

ขั้นตอน: B เรียงได้ "1245" → ใช้ 5 แทน 1, ใช้ 4 แทน 2, ใช้ 2 แทน 0 → "5424" (หลัก 4 คงเดิมเพราะ B หมดแล้ว)

การทำงานแบบละเอียด

กรณีพิเศษ

• B มีหลักน้อยกว่า A: ใช้จนหมด B แล้วหยุด
• B มีหลักมากกว่า A: ใช้แค่จำนวนหลักของ A
• ไม่มีการแทนที่: คืนค่า A เดิม
• Leading zero: หาก A นำหน้าด้วย 0 การแทนที่อาจทำให้ค่าลดลง ควรตรวจสอบเพิ่มเติม