โปรแกรมหาค่าจำนวนเต็มขั้นต่ำหลังการสลับตัวเลขติดกันสูงสุด k ครั้งใน Python

ปัญหา

ให้สตริง num แทนจำนวนเต็มขนาดใหญ่ และค่า k เราสามารถสลับตัวเลขที่อยู่ติดกันได้สูงสุด k ครั้ง ต้องการหาค่าต่ำสุดที่เป็นไปได้

ตัวอย่าง

ถ้า num = "5432" และ k = 4 ผลลัพธ์คือ 2453 เพราะลำดับการสลับคือ: 5432 → 4532 → 4523 → 4253 → 2453

ขั้นตอนการแก้ปัญหา

1. min_num := เรียงตัวเลขของ num จากน้อยไปมาก
2. i := 0, to_find := 0
3. วนลูป بينما num != min_num และ k > 0 และ i < len(num):
   • หาดัชนี indx ของตัวเลข to_find เริ่มจากดัชนี i ใน num
   • بينما indx != -1:
     • ถ้า indx - i <= k:
       • สลับตัวเลข: num := num[:i] + num[indx] + num[i:indx] + num[indx+1:]
       • k := k - (indx - i)
       • i := i + 1
       • to_find := 0
       • หา indx ใหม่ของ to_find จาก i
     • มิฉะนั้น ออกจากลูป
   • to_find := to_find + 1
4. คืนค่า num

การนำไปใช้งาน (Python)

def solve(num, k):
    min_num = sorted(list(num))
    min_num = ''.join(min_num)
    i = 0
    to_find = 0
    while num != min_num and k > 0 and i < len(num):
        indx = num.find(str(to_find), i)
        while indx != -1:
            if indx - i <= k:
                num = num[:i] + num[indx] + num[i:indx] + num[indx+1:]
                k -= (indx - i)
                i += 1
                to_find = 0
                indx = num.find(str(to_find), i)
            else:
                break
        to_find += 1
    return num

num = "5432"
k = 4
print(solve(num, k))

อินพุต

"5432", 4

เอาต์พุต

2453