โจทย์
เลขโรมันใช้สัญลักษณ์ I = 1, V = 5, X = 10, L = 50, C = 100, D = 500 และ M = 1000 โดยเขียนเรียงจากค่ามากไปค่าน้อยแล้วนำค่ามาบวกกัน ยกเว้นคู่แบบลบ 6 คู่ ได้แก่ IV = 4, IX = 9, XL = 40, XC = 90, CD = 400 และ CM = 900 ให้แปลง n เป็นเลขโรมันในรูปแบบมาตรฐาน ซึ่งจะใช้คู่แบบลบแทนการเขียนสัญลักษณ์เดียวกันซ้ำสี่ตัวเสมอ (4 คือ IV ไม่ใช่ IIII)
จงเขียนฟังก์ชัน integer_to_roman(n)
อินพุต
n: จำนวนที่ต้องการแปลง
เอาต์พุต
คืนค่าเลขโรมันเป็นสตริงของตัวอักษรพิมพ์ใหญ่
เงื่อนไข
1 ≤ n ≤ 3999
ตัวอย่าง
อินพุต:
n = 1994
ผลลัพธ์ที่คาดหวัง:
expected = "MCMXCIV"
อินพุต:
long long n = 1994;
ผลลัพธ์ที่คาดหวัง:
std::string expected = "MCMXCIV";
อินพุต:
long n = 1994;
ผลลัพธ์ที่คาดหวัง:
string expected = "MCMXCIV";
คำอธิบาย
1000 + 900 + 90 + 4 ได้ M, CM, XC, IV จึงเป็น "MCMXCIV"
อินพุต:
n = 58
ผลลัพธ์ที่คาดหวัง:
expected = "LVIII"
อินพุต:
long long n = 58;
ผลลัพธ์ที่คาดหวัง:
std::string expected = "LVIII";
อินพุต:
long n = 58;
ผลลัพธ์ที่คาดหวัง:
string expected = "LVIII";
คำอธิบาย
50 + 5 + 3 ได้ L, V, III จึงเป็น "LVIII"
แนวทางการแก้
ลองทำเองก่อน แล้วค่อยเปิดคำใบ้ทีละข้อ
คำใบ้ 1
รวมสัญลักษณ์และคู่แบบลบทั้งหกคู่ไว้ในรายการเดียว เรียงตามค่า
คำใบ้ 2
เลือกค่าที่มากที่สุดที่ยังไม่เกินส่วนที่เหลือซ้ำไปเรื่อย ๆ
คำใบ้ 3
ลองแปลง 4, 9 และ 3999 ด้วยมือเพื่อตรวจสอบตาราง
ความซับซ้อนที่คาดหวัง
เวลา O(1), หน่วยความจำเพิ่ม O(1)
แหล่งอ้างอิง
โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน