###### tags: `Math`
<h1>
Leetcode 12. Integer to Roman
</h1>
<ol>
<li>問題描述</li>
Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.<br>
<br>

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

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:
<ul>
<li>I can be placed before V (5) and X (10) to make 4 and 9.</li>
<li>X can be placed before L (50) and C (100) to make 40 and 90.</li>
<li>C can be placed before D (500) and M (1000) to make 400 and 900.</li>
</ul>
Given an integer, convert it to a roman numeral.

Example:

Input: s = "MCMXCIV"
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

<li>Input的限制</li>
<ul>
<li>1 <= num <= 3999</li>
</ul>
<br>

<li>思考流程</li>
<ul>
<li>切割整數位元</li>
從 input 整數的個位數開始切割，獲得個、十、百、千這四個位數的數字。再利用 table 針對不同位數準備代表性的羅馬數字( 像是個位數就是 I, V, X )，然後對 input 整數切割下來後的數字進行對應的處理，並且 append 進要回傳的 output 字串。
<br>
<br>
因為 input number 的大小是有上限的，所以 time complexity 是 O(1)。羅母字母的表示字母也是有限的，所以 space complexity 是 O(1)。
<br>
<br>
Time Complexity: O(1); Space Complexity: O(1)
<br>
<br>
</ul>
<li>測試</li>
<ul>
<li>test 1</li>
Input: num = 1409 ; Output: "MCDIX"
<li>test 2</li>
Input: num = 3888 ; Output: "MMMDCCCLXXXVIII"
<li>input size is not limited( edge case )</li>
如果對 input 的整數沒有設定上限( 在電腦系統的允許值內 )，則依據 input 增加的位數來影響演算法的執行時間，time complexity 會變成 O(log n)。
<li>Invalid input( edge case )</li>
如果出現正整數以外的數字，則羅馬字母無法表示，要出現錯誤訊息。
</ol>