Practical Algorithmsโจทย์ข้อ Cars
ข้อนี้เน้นเรื่องเวลามากกกๆ ความยากมันก็เลยเพิ่มขึ้น แต่ตัวโจทย์ไม่ได้ยากอะไรแค่ต้องสังเกตดีๆ
โจทย์(ฉบับย่อ)
ความยาก ★★★☆☆
มีรถที่จะแข่งในงานทั้งหมด N คัน (N ไม่เกิน 1,000,000) แต่ละคันมีความเร็วหน่วยต่อวินาทีที่ไม่ซ้ำกัน และความเร็วเป็นจำนวนเต็มในช่วง 1 - 2,000,000 หน่วยต่อวินาที ทีมงานที่จัดแข่งรถต้องการที่จะให้รถออกตัวที่เวลาแตกต่างกัน (ไม่ออกตัวในเวลาเดียวกัน) โดยที่ไม่ให้มีการแซงกันระหว่างรถคันใดๆ เลย
ทางทีมงานอยากจะรู้ว่า รถที่ต้องออกตัวเป็นลำดับที่ K จะมีความเร็วเท่าไหร่ โดยสมมติว่าทุกคันออกตัวจากจุดเดียวกัน และสนามมีความยาวมากๆ(K ไม่เกิน N)
โจทย์เต็มข้อ Carsข้อมูลนำเข้า
บรรทัดแรก : รับจำนวนเต็ม N และ K
N แทนจำนวนรถที่แข่งทั้งหมด (2 ≤ N ≤ 1,000,000)
K แทนลำดับรถคันที่ปล่อยตัว (1 ≤ K ≤ N)
บรรทัดที่ 2 ถึง N + 1 : แต่ละบรรทัด มีจำนวนเต็มหนึ่งจำนวน ระบุความเร็วรถคันที่ i โดยจะมีความเร็วในช่วง 1 - 2,000,000 หน่วยต่อวินาที และความเร็วทุกคันไม่ซ้ำกันเลย
ข้อมูลส่งออก
ความเร็วของรถที่ออกตัวเป็นลำดับที่ K ถ้าปล่อยในรูปแบบที่ไม่มีการแซงกัน รับประกันว่ามีรูปแบบการออกตัวของรถอย่างน้อย 1 วิธีที่เป็นไปได้
ตัวอย่าง
| Input | Output |
|---|---|
| 5 4 7 1 8 3 2 | 2 |
คำใบ้
ลองเอาตัวอย่างจากโจทย์มาขยายเพิ่มนิดนึง:
คันที่ 3: วิ่งด้วยความเร็ว 8 หน่วย ที่เป็นความเร็วที่เยอะที่สุด จากในตัวอย่าง
แปลว่าไม่มีคันไหนเลยที่ควรปล่อยก่อนคันที่ 3 เพราะ คันที่ 3 แซงได้ทั้งหมด (เนื่องจากสนามมีขนาดไม่จำกัด)
ก็เลยเอามาสรุปต่อได้ว่า
คันที่เร็วที่สุดจะต้องออกตัวก่อนคันอื่นเสมอ
คิดออกกันรึยังว่าต้องเรียงรถยังไง?
วิเคราะห์โจทย์
จากที่เราวิเคราะห์ได้แล้วว่า คันที่เร็วที่สุดต้องออกตัวก่อน เราสามารถใช้หลักการเดียวกันคิดว่า
ถ้าคันที่เร็วสุดออกตัวไปแล้ว ก็ต้องส่งคันที่เร็วรองลงมาตามไป เพื่อจะได้ไม่เกิดการแซงกัน จากข้อสังเกตนี้ทำให้สรุปได้ว่าลำดับของรถที่ต้องส่งไปจะต้อง
เรียงจากความเร็วของรถ โดยเรียงจากมากไปน้อย
โจทย์ครั้งนี้ก็เลยเปลี่ยนจากหารถคันที่ K กลายเป็น หาเลขที่มากเป็นลำดับที่ K แทน ถ้าจะเอาเลขทั้ง N ตัวมาเรียงผ่านการใช้คำสั่งในคอมพิวเตอร์ตรงๆ แล้วตอบเลย ก็ผ่านได้แหละ แต่เวลาที่ใช้ในการรันก็จะเยอะหน่อย
แต่อีกวิธีนึงที่เร็วกว่าคือ เราจะสร้าง array อีกชุดนึงขึ้นมาทั้งหมด 2,000,000 ช่อง จะเรียกว่า array v เพื่อเก็บค่าว่ามีเลขค่านั้นๆ อยู่มั้ย
โดยเราจะให้ v[i] = 1 ถ้ามีเลขค่า i อยู่ในข้อมูลที่ได้รับมา ส่วนช่องอื่นๆที่ไม่มี จะมีค่าเป็น 0
รูป array v ตามตัวอย่าง
ซึ่งการทำแบบนี้เรียกว่า การทำแฮชชิง (Hashing) และเราสามารถเอามาใช้ต่อในการหาเลขที่มากเป็นลำดับที่ K ได้
ทีนี้พอ Hashing เสร็จแล้ว เราก็จะเริ่มไล่ดูจากช่องท้ายสุดแล้วค่อยๆ ไปที่ค่าน้อยลงเรื่อยๆ ระหว่างนั้นก็จะนับว่ามีค่าที่มากกว่าหรือเท่ากับ หมายเลขช่องที่ดูอยู่ทั้งหมดกี่ตัวแล้ว ซึ่งคือนับช่องที่เก็บ 1 ระหว่างทางทั้งหมด พอครบ K ตัวก็ตอบหมายเลขช่องนั้นได้เลย
สมมติจะหาค่าเมื่อ K = 3 เพื่อให้อธิบายง่าย เราจะเริ่มที่ช่องที่มากที่สุด (ช่อง 8) ถึงช่องที่ 8 จะผ่านช่องที่เก็บ 1 ทั้งหมด 1 ช่อง แล้วไปดูช่องซ้ายต่อ
???
ถึงช่องที่ 7 จะผ่านช่องที่เก็บ 1 ทั้งหมด 2 ช่อง แล้วไปดูช่องซ้ายต่อ
???
ถึงช่องที่ 6 จะผ่านช่องที่เก็บ 1 ทั้งหมด 2 ช่อง แล้วไปดูช่องซ้ายต่อซึ่งช่อง 4 กับ 5 ทำแบบเดียวกัน
???
ถึงช่องที่ 3 จะผ่านช่องที่เก็บ 1 ทั้งหมด 3 ช่อง ซึ่งเท่ากับ Kดังนั้นตอบ 3 (จากที่เจอครบที่ตำแหน่ง 3)
???
จริงๆ ก็มีวิธีอื่นที่ทำได้เร็วพอๆ กับ Hashing อยู่เหมือนกันใครคิดออกก็มาคุยกันได้ใน comment นะครับ
เพจเรื่องเล่าชาวอัลกอ ข้อ Cars
