package leetcode;

import java.util.HashMap;

public class demo_12 {
    public String intToRoman(int num) {
        String s="";
        HashMap<Integer, String> hm= new HashMap<Integer, String>();
        hm.put(1,"I");
        hm.put(5, "V");
        hm.put(10, "X");
        hm.put(50, "L");
        hm.put(100, "C");
        hm.put(500, "D");
        hm.put(1000, "M");
        hm.put(4, "IV");
        hm.put(9, "IX");
        hm.put(40, "XL");
        hm.put(90, "XC");
        hm.put(400, "CD");
        hm.put(900, "CM");
        int[] key= {1,4,5,9,10,40,50,90,100,400,500,900,1000};
        int count=0;
        while(num>0) {
            for(int i=0;i<key.length;i++) {
                if(num>=1000) {
                    count=num/1000;
                    for(int j=0;j<count;j++) {
                        s=s+hm.get(key[key.length-1]);
                    }
                    num=num-count*key[key.length-1];
                    break;
                }
                if(num<key[i]) {
                    count = num/key[i-1];
                    for(int j=0;j<count;j++) {
                        s=s+hm.get(key[i-1]);
                    }
                    num=num-count*key[i-1];
                    break;
                }
            }
        }
        System.out.println(s);
        return s;
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        demo_12 d12=new demo_12();
        d12.intToRoman(58);
    }

}