หาตัวเลขสูงสุดที่สร้างได้จากการสลับสูงสุด K ครั้งใน C++

บทนำ

โจทย์: กำหนดตัวเลข n และจำนวนครั้งสลับสูงสุด k หาตัวเลขสูงสุดที่สร้างได้จากการสลับตัวเลขไม่เกิน k ครั้ง

ตัวอย่าง

n = 538, k = 1 → สลับ 5 กับ 8 ได้ 835 (สูงสุด)

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

ใช้ Backtracking (DFS) ลองสลับทุกคู่ที่เป็นไปได้ (i, j) โดยที่ i < j และ digit[i] < digit[j] (สลับเพื่อให้ใหญ่ขึ้น) แล้ว Recursive ด้วย k-1 เก็บค่าสูงสุดที่เจอ

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

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

void calcMaxNumAfterSwap(string number, int k, string& maxString, int n) {
    if (k == 0) return;
    for (int i = 0; i < n - 1; i++) {
        for (int j = i + 1; j < n; j++) {
            if (number[i] < number[j]) {
                swap(number[i], number[j]);
                if (number.compare(maxString) > 0)
                    maxString = number;
                calcMaxNumAfterSwap(number, k - 1, maxString, n);
                swap(number[i], number[j]); // backtrack
            }
        }
    }
}

int main() {
    string str = "15263";
    int k = 3;
    int size = str.length();
    string maxString = str;
    calcMaxNumAfterSwap(str, k, maxString, size);
    cout << "The maximum number created after " << k << " swaps is " << maxString;
    return 0;
}

ผลลัพธ์

The maximum number created after 3 swaps is 65321

คำอธิบาย

15263 → สลับได้ 65321 (เรียงจากมากไปน้อย) ใช้ 3 ครั้ง: 1↔6, 5↔5(ไม่สลับ), 2↔3 → ได้ 65321

ความซับซ้อน

เวลา: O((n²)^k) = O(n^(2k)) แบบ Exponential เหมาะสำหรับ n, k เล็ก (n ≤ 10, k ≤ 5) สำหรับค่ามากต้องใช้ Greedy + Heuristic

สรุป

Backtracking หาคำตอบที่ดีที่สุดสำหรับ k swaps ใช้ string compare หาค่าสูงสุด