โจทย์
แปลงเลขโรมันที่ถูกต้องให้เป็นค่าตัวเลขจำนวนเต็ม สัญลักษณ์ได้แก่ I=1, V=5, X=10, L=50, C=100, D=500, M=1000; หากมีสัญลักษณ์ที่มีค่าน้อยกว่าอยู่หน้าสัญลักษณ์ที่มีค่ามากกว่า ให้นำค่านั้นไปลบ (เช่น IV = 4, CM = 900)
ให้เขียนฟังก์ชัน roman_to_int(text)
อินพุต
text: เลขโรมันที่ถูกต้องหนึ่งค่า
เอาต์พุต
คืนค่าตัวเลขจำนวนเต็มที่สอดคล้องกับเลขโรมันนั้น
เงื่อนไข
1 ≤ value ≤ 3,999
ตัวอย่าง
ตัวอย่างที่ 1
อินพุต:
text = "XIV"
ผลลัพธ์ที่คาดหวัง:
expected = 14อินพุต:
std::string text = "XIV";
ผลลัพธ์ที่คาดหวัง:
long long expected = 14;อินพุต:
string text = "XIV";
ผลลัพธ์ที่คาดหวัง:
long expected = 14;คำอธิบาย
X = 10, IV = 4: 14
ตัวอย่างที่ 2
อินพุต:
text = "MCMXCIV"
ผลลัพธ์ที่คาดหวัง:
expected = 1994อินพุต:
std::string text = "MCMXCIV";
ผลลัพธ์ที่คาดหวัง:
long long expected = 1994;อินพุต:
string text = "MCMXCIV";
ผลลัพธ์ที่คาดหวัง:
long expected = 1994;คำอธิบาย
M=1000, CM=900, XC=90, IV=4: 1994
แนวทางการแก้
ลองทำเองก่อน แล้วค่อยเปิดคำใบ้ทีละข้อ
คำใบ้ 1
สัญลักษณ์ส่วนใหญ่บวกค่า แต่บางคู่จะลบเมื่อสัญลักษณ์ที่น้อยกว่าอยู่ก่อนตัวที่มากกว่า
คำใบ้ 2
ไล่จากซ้ายไปขวา แล้วเปรียบเทียบแต่ละสัญลักษณ์กับตัวถัดไป
คำใบ้ 3
ต้องจัดการสัญลักษณ์ตัวสุดท้ายให้ถูกต้องเสมอ เพราะมันไม่มีตัวถัดไป
ความซับซ้อนที่คาดหวัง
เวลา O(n), หน่วยความจำเพิ่ม O(1)
แหล่งอ้างอิง
โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน