12. integer to Roman numeral

Roman numerals contain the following seven characters ： I, V, X, L,C,D and M.

character The number
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
for example , Rome digital 2 Write to do II , Two parallel 1.12 Write to do XII , That is to say X + II . 27 Write to do XXVII, That is to say XX + V + II .

Usually , The small numbers in roman numbers are to the right of the big ones . But there are special cases , for example 4 Do not write IIII, It is IV. Numbers 1 In number 5 Left side , The number represented is equal to the large number 5 Decimal reduction 1 Value obtained 4 . similarly , Numbers 9 Expressed as IX. This special rule only applies to the following six cases ：

I Can be placed in V (5) and X (10) Left side , To express 4 and 9.
X Can be placed in L (50) and C (100) Left side , To express 40 and 90.
C Can be placed in D (500) and M (1000) Left side , To express 400 and 900.
Give you an integer , Turn it into Roman numerals .

Example 1:

 Input : num = 3
 Output : "III"

Example 2:

 Input : num = 4
 Output : "IV"

Example 3:

 Input : num = 9
 Output : "IX"

Example 4:

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

Example 5:

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

Tips ：

1 <= num <= 3999

1. enumeration

class Solution {
    
public:
    
    string intToRoman(int num) {
    
  
        string str="";
        
        while(num){
    
            if(num>=1000){
    
                num-=1000;
                str+="M";
            }
            else if(num>=900){
    
                num-=900;
                str+="CM";
            }
            else if(num>=500){
    
                num-=500;
                str+="D";
            }
            else if(num>=400){
    
                num-=400;
                str+="CD";
            }
            else if(num>=100){
    
                num-=100;
                str+="C";
            }
            else if(num>=90){
    
                num-=90;
                str+="XC";
            }
            else if(num>=50){
    
                num-=50;
                str+="L";
            }
            else if(num>=40){
    
                num-=40;
                str+="XL";
            }
            else if(num>=10){
    
                num-=10;
                str+="X";
            }
            else if(num>=9){
    
                num-=9;
                str+="IX";
            }
            else if(num>=5){
    
                num-=5;
                str+="V";
            }
            else if(num>=4){
    
                num-=4;
                str+="IV";
            }
            else if(num>=1){
    
                num-=1;
                str+="I";
            }
        
        }
        return str;

        

    }
};

2. greedy

class Solution {
    
public:
    
    string intToRoman(int num) {
    
  
        int values[13]={
    1000,900,500,400,100,90,50,40,10,9,5,4,1};
        string rom[13]={
    "M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};

        string str="";
        
        for(int i=0;i<13;i++){
    
            while(num>=values[i]){
    
                
                str+=rom[i];
                num-=values[i];
            }
        }

        return str;

        

    }
};