เจอโจทย์ใหม่ จะรู้ได้ยังไงว่าใช้หมวดไหน

ปัญหาที่เจอกันทุกคนหลังเรียนจบหลายหมวด: เข้าหน้าหมวด Sliding Window ก็แก้โจทย์ sliding window ได้ เข้าหน้า Two Pointers ก็แก้ได้ แต่พอเจอโจทย์เปล่า ๆ ที่ไม่มีป้ายบอกว่าอยู่หมวดไหน ก็นึกไม่ออกว่าจะเริ่มจากอะไร นั่นไม่ใช่เพราะยังไม่เก่งพอ แต่เพราะทักษะ "เลือกเครื่องมือ" เป็นทักษะแยกอีกอันหนึ่ง ที่ไม่ได้มาฟรีจากการฝึกแต่ละหมวด

หน้านี้จะให้เครื่องมือสามชั้น ใช้ตามลำดับ: อ่าน constraint เพื่อเดาความเร็วที่ต้องได้ ก่อน แล้วดูรูปร่างข้อมูล แล้วดูคำที่โจทย์ใช้ ชั้นแรกเป็นชั้นที่คนมองข้ามที่สุดแต่ตัดตัวเลือกได้เยอะที่สุด

ชั้นที่ 1 · อ่าน constraint แล้วเดา Big-O ที่ต้องได้

โจทย์ทุกข้อบอกขนาดข้อมูลสูงสุดไว้ในส่วน constraint และตัวเลขนั้นบอกใบ้ว่าคำตอบต้องเร็วระดับไหน ซึ่งแปลกลับไปเป็นหมวดที่เป็นไปได้ ระบบตรวจส่วนใหญ่ให้เวลาประมาณ 1 วินาที ซึ่งรันคำสั่งได้ราว ๆ 100 ล้านครั้ง ลองดูว่าแต่ละขนาดข้อมูลทำให้อะไรเป็นไปไม่ได้

import math

LIMIT = 100_000_000          # จำนวนคำสั่งคร่าว ๆ ที่รันจบใน ~1 วินาที

print(f"{'n':>10} | {'O(n)':>14} | {'O(n log n)':>14} | {'O(n^2)':>18} | ผ่านได้ถึง")
for n in [20, 500, 5_000, 100_000, 1_000_000]:
    a = n
    b = n * max(1, int(math.log2(n)))
    c = n * n
    ok = "O(n^2)" if c <= LIMIT else ("O(n log n)" if b <= LIMIT else "O(n)")
    print(f"{n:>10,} | {a:>14,} | {b:>14,} | {c:>18,} | {ok}")

         n |           O(n) |     O(n log n) |             O(n^2) | ผ่านได้ถึง
        20 |             20 |             80 |                400 | O(n^2)
       500 |            500 |          4,000 |            250,000 | O(n^2)
     5,000 |          5,000 |         60,000 |         25,000,000 | O(n^2)
   100,000 |        100,000 |      1,600,000 |     10,000,000,000 | O(n log n)
 1,000,000 |      1,000,000 |     19,000,000 |  1,000,000,000,000 | O(n log n)

สังเกตว่าที่ n = 100,000 คอลัมน์ O(n²) พุ่งไปหนึ่งหมื่นล้าน คือเกินงบไป 100 เท่า นั่นแปลว่าถ้าโจทย์บอก n ถึงแสน แล้วเรากำลังคิดวิธีที่มี loop ซ้อนสองชั้น ให้รู้ตัวได้เลยว่าคิดผิดทางแล้ว ไม่ต้องเสียเวลาเขียนให้เสร็จก่อนแล้วค่อยรู้ ในทางกลับกันถ้า n เล็กมากอย่าง 20 แปลว่าโจทย์ กำลังอนุญาต ให้เราทำวิธีที่ช้าเวอร์อย่างการลองทุกความเป็นไปได้ ซึ่งเป็นใบ้ที่ตรงตัวมาก

ชั้นที่ 2 · รูปร่างข้อมูลตัดหมวดให้เหลือไม่กี่อัน

ก่อนดูว่าโจทย์ถามอะไร ให้ดูว่าโจทย์ ให้อะไรมา รูปร่างของข้อมูลตัดหมวดออกไปได้ทันทีเป็นกลุ่ม ๆ

ชั้นที่ 3 · คำที่โจทย์ใช้ → หมวด

ชั้นนี้คือตารางที่ใช้บ่อยที่สุดเวลาฝึก ให้มองหาคำหรือรูปคำถามในโจทย์ แล้วเทียบกับแถวเหล่านี้

คู่ที่คนสับสนกันบ่อยที่สุด

ถ้าตัดเหลือสองหมวดแล้วยังเลือกไม่ได้ ให้ดูตารางนี้ — แต่ละแถวคือคำถามหนึ่งคำถามที่แยกสองหมวดออกจากกันได้เด็ดขาด

ถ้ามันไม่เข้าหมวดไหนเลย

จะมีโจทย์ที่ดูแล้วไม่ตรงกับแถวไหนในตารางข้างบนเลย ตอนนั้นห้ามนั่งนึกชื่อหมวดต่อ เพราะมันไม่มาเอง ให้เปลี่ยนไปทำสามขั้นนี้แทน ซึ่งเป็นวิธี สร้าง คำตอบ ไม่ใช่การ จำ คำตอบ

1. เขียนวิธีที่ช้าที่สุดแต่ถูกแน่ ๆ ให้ได้ก่อน (brute force) โดยไม่สนความเร็วเลย ถ้าเขียนขั้นนี้ไม่ได้ แปลว่ายังไม่เข้าใจโจทย์ ไม่ใช่ยังไม่รู้เทคนิค
2. หาว่ามันทำงานอะไรซ้ำ ๆ โดยไม่จำเป็น — ทุกเทคนิคเร็ว ๆ ในคอร์สนี้เกิดจากการกำจัดงานซ้ำแบบใดแบบหนึ่งทั้งนั้น
3. จับคู่ชนิดของงานซ้ำกับเทคนิค ตามตารางด้านล่าง