โจทย์ "เติมวงเล็บ"
ให้สตริงที่ประกอบไปด้วยวงเล็บเปิด ‘(‘ และวงเล็บปิด ‘)’ จงคำนวณหาจำนวนวงเล็บเปิดหรือปิดที่น้อยที่สุดที่ต้องเติมในสตริงดังกล่าว เพื่อทำให้วงเล็บเปิดและปิดจับคู่กันได้อย่างถูกต้อง (สำหรับนิยามอย่างเป็นทางการของการจับคู่ได้อย่างถูกต้องดูได้จากส่วนอธิบายเพิ่มเติมท้ายโจทย์)
งานของคุณ
เขียนโปรแกรมรับสตริงที่ประกอบด้วยวงเล็บเปิดและวง เล็บปิด จากนั้นคำนวณหาจำนวนวงเล็บที่ต้องเติมเข้าไปในสตริงดังกล่าว เพื่อให้เป็นสตริงที่วงเล็บเปิดและปิดจับคู่กันได้อย่างถูกต้อง
ข้อมูลนำเข้า
มีบรรทัดเดียวเป็นสตริงที่ประกอบด้วยวงเล็บเปิดและวงเล็บปิด ความยาวไม่เกิน 200 ตัวอักษร
ข้อมูลส่งออก
มีหนึ่งบรรทัด เป็นจำนวนเต็มแทนจำนวนวงเล็บที่น้อยที่สุดที่ต้องเติมเข้าไปในสตริงเพื่อให้เป็นสตริงที่ถูกต้อง
คำอธิบายเพิ่มเติม (ไม่จำเป็นนักต่อการทำโจทย์)
สำหรับสตริงที่ประกอบไปด้วยวงเล็บเปิดและวงเล็บปิด เราจะกล่าวว่าสตริงดังกล่าวมีการจับกันของวงเล็บเปิดและปิดอย่างถูกต้อง ก็ต่อเมื่อเราสามารถจับคู่วงเล็บเปิดกับวงเล็บปิดได้แบบ 1 ต่อ 1 โดยที่สอดคล้องกับเงื่อนไขต่อไปนี้: ถ้าวงเล็บเปิดที่เป็นอักขระที่ i จับคู่กับวงเล็บปิดที่เป็นอักขระที่ j ในสตริง เราจะได้ว่า
- i < j (วงเล็บเปิดอยู่หน้าวงเล็บปิด)
- สำหรับวงเล็บเปิดใด ๆ ที่อยู่ที่ตำแหน่ง a ที่ i < a < j, วงเล็บเปิดนั้นจะต้องจับคู่กับวงเล็บปิดที่อยู่ที่ตำแหน่ง b ที่ a < b < j เท่านั้น
- และในทางกลับกัน วงเล็บปิดใด ๆ ที่อยู่ที่ตำแหน่ง a ที่ i < a < j, วงเล็บปิดนั้นจะต้องจับคู่กับวงเล็บเปิดที่อยู่ที่ตำแหน่ง b ที่ i < b < a เท่านั้น เช่นกัน
ที่มา : IOI Thailand League 2010 เดือนพฤษภาคม
ตัวอย่างข้อมูลนำเข้า ตัวอย่างข้อมูลส่งออก
())( 2
(()()))()) 2
ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้
ที่มาของโจทย์: www.programming.in.th
วิเคราะห์โจทย์
- รับค่าข้อมูลจำนวน 1 ค่า คือข้อมูลวงเล็บ
- ทำการตรวจสอบข้อมูลว่าข้อมูลต้องใส่วงเล็บอีกกี่ตัวจึงจะทำให้ ข้อมูลชุดนั้นถูกต้อง
เเนวคิดในการเเก้โจทย์
- ทำการตรวจสอบเป็นคู่เเล้วถอดออกจาก List ถ้าถูกต้อง เมื่อครบรอบการตรวจสอบก็จะได้ List ออกมาที่ทำการถอดคู่ที่ถูกต้องออกไปเเล้ว ถ้าเหลือเเสดงว่านั้นคือจำนวนวงเล็บที่ต้องเติม เเต้ถ้าไม่เหลือ เเสดงว่าข้อมูลนั้นถูกต้องเเล้ว
Code Python
Input_Data = input("กรุณาใส่ข้อมูลที่ต้องการตรวจสอบ : ")
List_Data = []
for i in range(len(Input_Data)):
List_Data.append(Input_Data[i])
for b in range(int((len(List_Data)/2)+1)):
for a in range(len(List_Data)-1):
if List_Data[a] == "(" and List_Data[a+1] == ")" :
List_Data.pop((a+1))
List_Data.pop(a)
break
print("มีวงเว็บที่ต้องใส่เพิ่มอีกจำนวน "+str(len(List_Data))+" วงเล็บ")
ผลลัพธ์ที่ได้...
กรุณาใส่ข้อมูลที่ต้องการตรวจสอบ : ())(
มีวงเว็บที่ต้องใส่เพิ่มอีกจำนวน 2 วงเล็บ
กรุณาใส่ข้อมูลที่ต้องการตรวจสอบ : (()()))())
มีวงเว็บที่ต้องใส่เพิ่มอีกจำนวน 2 วงเล็บ
กรุณาใส่ข้อมูลที่ต้องการตรวจสอบ : ()(())()
มีวงเว็บที่ต้องใส่เพิ่มอีกจำนวน 0 วงเล็บ
ไม่มีความคิดเห็น:
แสดงความคิดเห็น