Delete Columns to Make Sorted (ลบคอลัมน์ให้เรียงลำดับ) ใน Python

โจทย์: ให้ Array ของสตริงความยาวเท่ากัน ต้องการลบคอลัมน์ (Column) น้อยที่สุด เพื่อให้คอลัมน์ที่เหลือเรียงลำดับ Non-decreasing (จากบนลงล่าง)

Input/Output

Input:  ["cba", "daf", "ghi"]
Output: 1
# คอลัมน์ 0: c,d,g (เรียง), คอลัมน์ 1: b,a,h (ไม่เรียง), คอลัมน์ 2: a,f,i (เรียง)
# ลบคอลัมน์ 1 ทั้งหมด 1 คอลัมน์

อัลกอริทึม

1. Transpose Matrix: zip(*A) ได้คอลัมน์แต่ละคอลัมน์
2. เช็คแต่ละคอลัมน์ว่าเรียงแล้วหรือไม่ (sorted(col) == list(col))
3. นับคอลัมน์ที่ไม่เรียง = จำนวนที่ต้องลบ

ตัวอย่างโค้ด (One-liner)

class Solution:
    def minDeletionSize(self, A):
        return sum([1 - (sorted(col) == list(col)) for col in zip(*A)])

ob = Solution()
print(ob.minDeletionSize(["cba", "daf", "ghi"]))

ผลลัพธ์

1

การอธิบาย One-liner

• zip(*A) → Transpose rows เป็น columns
• sorted(col) == list(col) → True (1) ถ้าเรียง, False (0) ถ้าไม่เรียง
• 1 - ... → กลับค่า: 0 ถ้าเรียง, 1 ถ้าไม่เรียง (ต้องลบ)
• sum(...) → รวมจำนวนคอลัมน์ที่ต้องลบ

Complexity: O(M × N log N) โดย M = จำนวนสตริง, N = ความยาวสตริง (จากการ Sort แต่ละคอลัมน์)