12. Integer to Roman

Đề bài

Chữ số La Mã được biểu diễn bằng 7 ký hiệu:

Symbol       Value
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

Ví dụ:

• 2 được viết là II (hai số 1).
• 12 được viết là XII (X + II).
• 27 được viết là XXVII (XX + V + II).

Thông thường, chữ số La Mã được viết từ trái qua phải theo thứ tự giảm dần. Tuy nhiên có các trường hợp đặc biệt dùng quy tắc “trừ”:

• 4 không viết là IIII mà viết là IV (1 đứng trước 5 nghĩa là $5 - 1$).
• 9 viết là IX (10 - 1).

Cụ thể, chỉ có 6 trường hợp dùng phép trừ:

• I đặt trước V (5) và X (10) để tạo IV (4) và IX (9).
• X đặt trước L (50) và C (100) để tạo XL (40) và XC (90).
• C đặt trước D (500) và M (1000) để tạo CD (400) và CM (900).

Cho một số nguyên num, hãy chuyển nó sang chữ số La Mã.

Ví dụ 1:

Input: num = 3
Output: "III"

Ví dụ 2:

Input: num = 4
Output: "IV"

Ví dụ 3:

Input: num = 9
Output: "IX"

Ví dụ 4:

Input: num = 58
Output: "LVIII"
Explanation: L = 50, V = 5, III = 3.

Ví dụ 5:

Input: num = 1994
Output: "MCMXCIV"
Explanation: M = 1000, CM = 900, XC = 90 và IV = 4.

Ràng buộc:

• 1 <= num <= 3999

Tóm tắt đề

Chuyển số nguyên num (1..3999) sang chuỗi chữ số La Mã theo các ký hiệu và quy tắc ở trên (có cả các cặp đặc biệt: IV, IX, XL, XC, CD, CM).

Ý tưởng

Dùng tham lam (greedy):

• Chuẩn bị 2 mảng values và symbols đã sắp xếp từ lớn đến nhỏ, bao gồm cả các trường hợp đặc biệt (1000, 900, 500, 400, ... , 4, 1).
• Lặp cho tới khi num = 0:
  • Chọn giá trị lớn nhất values[i] sao cho values[i] <= num.
  • Trừ num -= values[i] và nối symbols[i] vào kết quả.

Code

package leetcode

func intToRoman(num int) string {
	values := []int{1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1}
	symbols := []string{"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"}
	res, i := "", 0
	for num != 0 {
		for values[i] > num {
			i++
		}
		num -= values[i]
		res += symbols[i]
	}
	return res
}

---