Integer to Roman: Greedy Mapping yang Selalu Muncul di Interview

Soal

Diberikan integer num, konversi ke string Roman numeral. Roman numeral dibentuk dari tujuh simbol dasar:

Aturan penting — subtractive notation. Angka seperti 4 tidak ditulis IIII, tapi IV (5 - 1). Begitu juga:

Constraints: 1 <= num <= 3999

Contoh:

Input:  num = 3749
Output: "MMMDCCXLIX"

Input:  num = 58
Output: "LVIII"

Intuisi — Greedy

Roman numeral selalu dibangun dari simbol terbesar yang muat. Ini bukan kebetulan — memang sifat dasar sistem numeral Romawi.

Ambil 58: simbol terbesar yang ≤ 58 adalah L (50). Sisanya 8. Simbol terbesar yang ≤ 8 adalah V (5). Sisanya 3. Tiga kali I. Hasil: "LVIII".

Ambil 3749: mulai dari M (1000) tiga kali → "MMM", sisa 749. Berikutnya D (500) → "MMMD", sisa 249. Berikutnya C (100) dua kali → "MMMDCC", sisa 49. Berikutnya XL (40) → "MMMDCCXL", sisa 9. Berikutnya IX (9) → "MMMDCCXLIX".

Polanya selalu sama: ambil simbol terbesar yang ≤ sisa, kurangi, ulangi.

Mapping yang Tepat

Kita perlu semua kemungkinan simbol — termasuk subtractive cases — diurutkan dari terbesar ke terkecil:

mapping := []struct {
    value  int
    symbol string
}{
    {1000, "M"}, {900, "CM"}, {500, "D"}, {400, "CD"},
    {100, "C"}, {90, "XC"}, {50, "L"}, {40, "XL"},
    {10, "X"}, {9, "IX"}, {5, "V"}, {4, "IV"},
    {1, "I"},
}

Tiga belas simbol. Urutan menurun. Kenapa 13? Karena kita memasukkan 6 subtractive cases ke dalam mapping sebagai simbol atomik. Ini membuat algoritma menjadi pure greedy — tidak perlu logika khusus untuk deteksi 4/9.

Solusi — Greedy O(1)

func intToRoman(num int) string {
    mapping := []struct {
        value  int
        symbol string
    }{
        {1000, "M"}, {900, "CM"}, {500, "D"}, {400, "CD"},
        {100, "C"}, {90, "XC"}, {50, "L"}, {40, "XL"},
        {10, "X"}, {9, "IX"}, {5, "V"}, {4, "IV"},
        {1, "I"},
    }

    var result strings.Builder
    for _, pair := range mapping {
        for num >= pair.value {
            result.WriteString(pair.symbol)
            num -= pair.value
        }
    }

    return result.String()
}

Visualisasi

num = 3749

value=1000 (M):  num=3749 → "M",   num=2749 → "M",   num=1749 → "M",   num=749 → stop (749 < 1000)
                  result = ["M","M","M"], num = 749

value=900  (CM): 749 < 900 → skip

value=500  (D):  749 ≥ 500 → "D", num = 249
                  result = ["M","M","M","D"], num = 249

value=400  (CD): 249 < 400 → skip

value=100  (C):  249 ≥ 100 → "C", num = 149 → "C", num = 49 → stop (49 < 100)
                  result = ["M","M","M","D","C","C"], num = 49

value=90   (XC): 49 < 90 → skip

value=50   (L):  49 < 50 → skip

value=40   (XL): 49 ≥ 40 → "XL", num = 9
                  result = ["M","M","M","D","C","C","XL"], num = 9

value=10   (X):  9 < 10 → skip

value=9    (IX): 9 ≥ 9 → "IX", num = 0
                  result = ["M","M","M","D","C","C","XL","IX"], num = 0

Join → "MMMDCCXLIX"

Kenapa Greedy Work?

Beberapa soal tidak bisa diselesaikan dengan greedy (contoh: coin change dengan denomination tertentu). Tapi soal ini selalu greedy-optimal karena:

1. Simbol Romawi membentuk canonical coin system — setiap kali kita ambil simbol terbesar yang muat, kita tidak akan masuk ke situasi di mana kombinasi simbol lebih kecil bisa menghasilkan representasi yang lebih pendek.
2. Constraint 1-3999 menjamin kita tidak perlu simbol di atas MMM (3000) atau special case di atas ribuan.

Kompleksitas

Karena constraint num ≤ 3999, kompleksitasnya konstan. Untuk general case (integer berapapun), tetap O(log n) karena jumlah simbol per digit terbatas.

Alternate Approach — Divide by Place Value

Ada juga pendekatan dengan memproses per digit (ribuan/ratusan/puluhan/satuan):

func intToRoman(num int) string {
    thousands := []string{"", "M", "MM", "MMM"}
    hundreds  := []string{"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"}
    tens      := []string{"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"}
    ones      := []string{"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"}

    return thousands[num/1000] +
           hundreds[(num%1000)/100] +
           tens[(num%100)/10] +
           ones[num%10]
}

Ini juga O(1) dan lebih eksplisit, tapi greedy version lebih fleksibel kalau aturan berubah.

Intisari

Sort symbols descending. While the number is large enough for a symbol, append it and subtract. Repeat.

Soal ini menguji apakah kamu bisa mengenali greedy choice property — bahwa memilih simbol terbesar yang muat tidak akan membatalkan solusi optimal. Sekali kamu sadar itu, implementasinya trivial.