/**
1. 二分找到最大的单位, 然后每次按单位从大到小减去即可
*/

class Solution {

    int[] unit = {1, 4, 5, 9, 10, 40, 50, 90, 100, 400, 500, 900, 1000};
    Map<Integer, String> roman = init();

    public String intToRoman(int num) {
        StringBuilder buffer = new StringBuilder();
        for (int i = lowerBound(num) ; num > 0 && i>= 0; i--){
            while (num >= unit[i] && num > 0){
                buffer.append(roman.get(unit[i]));
                num -= unit[i];
            }
        }
        return buffer.toString();
    }

    int lowerBound(int x) {
        int l = 0 , r = unit.length - 1;
        while( l < r ){
            int mid = l + r + 1 >> 1;
            if (x >= unit[mid]) l = mid;
            else r = mid - 1;
        }
        return l;
    }

    private Map<Integer, String> init(){
        Map<Integer, String> roman = new HashMap<>();
        roman.put(1, "I");
        roman.put(4, "IV");
        roman.put(5, "V");
        roman.put(9, "IX");
        roman.put(10, "X");
        roman.put(40, "XL");
        roman.put(50, "L");
        roman.put(90, "XC");
        roman.put(100, "C");
        roman.put(400, "CD");
        roman.put(500, "D");
        roman.put(900, "CM");
        roman.put(1000, "M");
        return roman;
    }
}