# 12. Integer to Roman

### Leetcode

<https://leetcode.com/problems/integer-to-roman/>

### 題目

Roman numerals are represented by seven different symbols: `I`, `V`, `X`, `L`, `C`, `D` and `M`.

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

For example, `2` is written as `II` in Roman numeral, just two one's added together. `12` is written as `XII`, which is simply `X + II`. The number `27` is written as `XXVII`, which is `XX + V + II`.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not `IIII`. Instead, the number four is written as `IV`. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as `IX`. There are six instances where subtraction is used:

* `I` can be placed before `V` (5) and `X` (10) to make 4 and 9.&#x20;
* `X` can be placed before `L` (50) and `C` (100) to make 40 and 90.&#x20;
* `C` can be placed before `D` (500) and `M` (1000) to make 400 and 900.

Given an integer, convert it to a roman numeral.

### 解答 <a href="#ti-jie" id="ti-jie"></a>

* **方法一**

由於題目限制 `1 <= num <= 3999`，所以我們可以利用貪婪算法，arr 列出所有可能的狀況，再一一遍歷 arr 求出羅馬字母

```
var intToRoman = function(num) {
    const arr = [
        {
            symbol: 'M',
            value: 1000
        },
        {
            symbol: 'CM',
            value: 900
        },
        {
            symbol: 'D',
            value: 500
        },
        {
            symbol: 'CD',
            value: 400
        },
        {
            symbol: 'C',
            value: 100
        },
        {
            symbol: 'XC',
            value: 90
        },
        {
            symbol: 'L',
            value: 50
        },
        {
            symbol: 'XL',
            value: 40
        },
        {
            symbol: 'X',
            value: 10
        },
        {
            symbol: 'IX',
            value: 9
        },
        {
            symbol: 'V',
            value: 5
        },
        {
            symbol: 'IV',
            value: 4
        },
        {
            symbol: 'I',
            value: 1
        },
    ]
    
    let res = '';
    for(let i=0; i<arr.length; i++) {
        const obj = arr[i];
        let quotient = Math.floor(num / obj.value);
        while(quotient--) {
            res += obj.symbol;
            num -= obj.value;
        }
    }
    return res;
};
```

Runtime: 144 ms, faster than 71.19% of JavaScript online submissions for Integer to Roman.

Memory Usage: 45 MB, less than 71.48% of JavaScript online submissions for Integer to Roman.

### 測資

```
let num = 58; // "LVIII"
num = 1994; // "MCMXCIV"

console.log(intToRoman(num))
```

### 參考資料

<https://www.cnblogs.com/grandyang/p/4123374.html>
